OI题库

某地区有m座煤矿，其中第i号矿每年产量为ai吨，现有火力发电站一个，每年需用煤b吨，每年运行的固定费用（包括折旧费，不包括煤的运费）为h元，每吨原煤从第i号矿运到原有发电厂的运费为Ci0（i=1，2，…，m；j=1，2，…，n）。
现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第i号备选厂址建新厂，每年运行的固定费用为hi元。每吨原煤从第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行：总费用

样例
factory.in
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

factory.out
8
49

数据范围
对于30%的数据，n<=50，m<=100，b<=100
对于60%的数据，n<=50，m<=100，b<=10000
对于所有数据，n<=50，m<=50000，b<=10000