工厂选址 ### 题目描述 某地区有 $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}$的值。 其中，$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$。 ### 输出描述 第一行一个整数表示选择的新发电厂的厂址编号，如有多个厂址满足条件，输出最小的一个； 第二行一个整数表示最小的年总费用。 ### 输入输出样例 #### 示例 1 >输入 ```txt 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 ``` >输出 ```txt 8 49 ```