#2426. [HAOI2010]工厂选址

题目描述

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

**现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂，每年运行的固定费用为h j元。每吨原煤从第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 **