427. [HAOI 2010]工厂选址

【题目描述】

某地区有 $m$ 座煤矿，其中第 $i$ 号矿每年产量为 $a_i$ 吨。现有一火力发电厂，每年需用煤恰好 $b$ 吨，每年运行的固定费用（不包括煤的运费）为 $h$ 元，每吨原煤从第 $i$ 号矿运到火力发电厂的运费为 $C_{i,0}$ 元。

现规划新建一个发电厂， $m$ 座煤矿每年开采的原煤将全部供给这两座发电厂。有 $n$ 个备选的新发电厂厂址，若在第 $j$ 号备选厂址建新厂，每年运行的固定费用为 $h_j$ 元；每吨原煤从第 $i$ 号矿运到第 $j$ 号备选厂址的运费为 $C_{i,j}$ 元。

试问：应如何选取新厂厂址并分配 $m$ 座煤矿开采的原煤，才能使每年的总费用（发电厂运行费用与原煤运费之和）最小。

【输入格式】

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

接下来一行 $m$ 个整数 $a_1,a_2,...,a_m$ 表示每一处煤矿的年产量。

接下来一行 $n$ 个整数 $h_1,h_2,...,h_n$ 表示新厂建在每一个位置的固定费用。

接下来 $n+1$ 行每行 $m$ 个正整数，第 $i$ 行描述 $C_{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

【数据规模与约定】

对于 $30\%$ 的数据，$n \leq 50，m \leq 100，b \leq 100$；

对于 $60\%$ 的数据，$n \leq 0，m \leq 100，b \leq 10000$；

对于 $100\%$ 的数据，$1 \leq m \leq 5 \times 10^4$，$1 \leq b \leq 10^4$，

$1 \leq n \leq 50$，$0 \leq h , h_i \leq 100$，$0 \leq a_i \leq 500$，

$\sum\limits_{i=1}^m a_i \geq b$，$0 \leq C_{i,j} \leq 50$。