#P2514. [HAOI2010] 工厂选址

[HAOI2010] 工厂选址

题目描述

某地区有 mm 座煤矿,其中第 ii 号矿每年产量为 aia_i 吨。现有一火力发电厂,每年需用煤恰好 bb 吨,每年运行的固定费用(不包括煤的运费)为 hh 元,每吨原煤从第 ii 号矿运到火力发电厂的运费为 Ci,0C_{i,0} 元。

现规划新建一个发电厂, mm 座煤矿每年开采的原煤将全部供给这两座发电厂。有 nn 个备选的新发电厂厂址,若在第 jj 号备选厂址建新厂,每年运行的固定费用为 hjh_j 元;每吨原煤从第 ii 号矿运到第 jj 号备选厂址的运费为 Ci,jC_{i,j} 元。

试问:应如何选取新厂厂址并分配 mm 座煤矿开采的原煤,才能使每年的总费用(发电厂运行费用与原煤运费之和)最小。

输入格式

第一行四个整数 m,b,h,nm,b,h,n

接下来一行 mm 个整数 a1,a2,...,ama_1,a_2,...,a_m 表示每一处煤矿的年产量。

接下来一行 nn 个整数 h1,h2,...,hnh_1,h_2,...,h_n 表示新厂建在每一个位置的固定费用。

接下来 n+1n+1 行每行 mm 个正整数,第 ii 行描述 C1,i1,C2,i1,...,Cm,i1C_{1,i-1} , C_{2,i-1} , ... , C_{m , i-1}的值。

输出格式

第一行一个整数表示选择的新发电厂的厂址编号,如有多个厂址满足条件,输出最小的一个;

第二行一个整数表示最小的年总费用。

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 

提示

对于100%100 \%的数据,1m5×1041 \leq m \leq 5 \times 10^41b1041 \leq b \leq 10^41n501 \leq n \leq 500h,hi1000 \leq h , h_i \leq 1000ai5000 \leq a_i \leq 500i=1maib\sum\limits_{i=1}^m a_i \geq b0Ci,j500 \leq C_{i,j} \leq 50