Background

Special for beginners, ^_^

Description

某地区有m座煤矿，其中第i号矿每年产量为a~i~吨，现有火力发电厂一个，每年需用煤b吨，每年运行的固定费用（包括折旧费，不包括煤的运费）为h元，每吨原煤从第i号矿运到原有发电厂的运费为C ~i0~ （i=1，2，…，m）。

现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂，每年运行的固定费用为h~j~元。每吨原煤从第i号矿运到j号备选厂址的运费为C ~ij~ （i=1，2，…，m；j=1，2，…，n）。

**试问：应把新厂厂址选取在何处？m座煤矿开采的原煤应如何分配给两个发电厂，才能使每年的总费用（发电厂运行费用与原煤运费之和）为最小。 **

Format

Input

第1行： m b h n

**第2行： a~1~ a~2~ … a~m~ ** （0<=a ~i~ <=500, a ~1~ +a ~2~ +...+a ~n~ >=b ）

**第3行： h~1~ h~2~ … h~n~ ** （0<=h ~i~ <=100 ）

**第4行： C~10~ C~20~ … C~m0~ ** （0<=Cij<=50 ）

第5行： C~11~ C~21~ … C~m1~

** … …**

第****n+4行：C~1n~ C~2n~ … C~mn~

Output

第1行：新厂址编号，如果有多个编号满足要求，输出最小的。

**第2行：总费用 **

Samples

4 2 7 9
3 1 10 3
6 3 7 1 10 2 7 4 9
1 2 4 3
6 6 8 2
4 10 8 4
10 2 9 2
7 6 6 2
9 3 7 1
2 1 6 9
3 1 10 9
4 2 1 8
2 1 3 4

8
49

Limitation

**对于所有数据, n<=50, m<=50000, b<=10000 **