题目描述

某地区有 $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,\dots,a_m$ 表示每一处煤矿的年产量。

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

接下来 $n+1$ 行每行 $m$ 个正整数，第 $i$ 行描述 $C_{1,i-1},C_{2,i-1},\dots,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\%$ 的数据，$1\le m \le 5\times 10^4$，$1\le b\le 10^4$，$0\le h,h_i\le 100$，$1\le n\le 50$，$0\le a_i\le 500$，$\sum \limits_{i=1}^m a_i\ge b$，$0\le C_{i,j}\le 50$。

题目来源

Day2