ZDM能源公司现有一个火力发电厂和M座煤矿。火力发电厂每年需要用煤T吨。该火力发电厂每年正常运作的固定费用为R元（包括人员工资，折旧费，不包括煤的运费）。第I号煤矿每年产量为ai吨，每吨原煤从第I号煤矿运到该火力发电厂的运费为Ci0。 
ZDM能源公司现在准备再建立一个火力发电厂，M座煤矿每年开采的原煤将全部供给这两座发电厂。现有N个备选的地址建厂。若在第J号备选地址建厂，新建发电厂每年正常运作的固定费用每年运行的固定费用为hj元。每吨原煤从第I号矿运到J号备选厂址的运费为Cij。 
现在的问题是，把新厂地址选取什么位置，M座煤矿开采的原煤应如何分配给两个发电厂，才能使ZDM能源公司每年的总费用（发电厂运行费用与原煤运费之和）达到最小。 

第1行：      M  T  R  N 
第2行：      a1  a2 …  am   
第3行：      h1  h2 …  hn 
第4行：       C10 C20 … Cm0 
第5行：       C11 C21 … Cm1 
                        …   … 
第n+4行：  C1n C2n … Cmn 



1≤M≤100000   1≤T≤10000    1≤R≤50     1≤N≤50
0≤ai≤500,   a1+a2+...+am>=T   0≤ hj ≤100   0≤Ci0，Cij ≤50
  所有数据都是整数。 数据之间有一个空格。        i=1,2,…., m   j=1,2,…, n

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

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