[HAOI2010]工厂选址

时间限制:10s      空间限制:128MB

题目描述

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

 

现规划新建一个发电厂,m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂,每年运行的固定费用为hj元。每吨原煤从第i号矿运到j号备选厂址的运费为Cij(i=1,2,…,m;j=1,2,…,n)。

 

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


输入格式

第1行:      m  b  h  n

第2行:      a1  a2 …  am 0<=ai<=500, a1+a2+...+an>=b

第3行:      h1  h2 …  hn 0<=hi<=100

第4行:      C10 C20 … Cm0 0<=Cij<=50

第5行:      C11 C21 … Cm1

                              …   …

n+4行:C1n C2n … Cmn


输出格式

第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 

提示

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


题目来源

Day2