[HAOI2010]工厂选址

某地区有 $m$ 座煤矿，其中第 $i$ 座煤矿的年产量为 $a_i$ 吨。现有一座火力发电厂，每年需要原煤 $b$ 吨，其每年运行的固定费用（包括折旧费，不包括原煤运费）为 $h$ 元。将每吨原煤从第 $i$ 座煤矿运往现有发电厂的费用为 $C_{i0}$，其中 $i=1,2,\dots,m$。

现计划新建一座发电厂，$m$ 座煤矿每年开采的原煤将全部供应给这两座发电厂。现有 $n$ 个备选厂址。若在第 $j$ 个备选厂址建设新发电厂，其每年运行的固定费用为 $h_j$ 元；将每吨原煤从第 $i$ 座煤矿运往该厂址的费用为 $C_{ij}$，其中 $i=1,2,\dots,m$，$j=1,2,\dots,n$。

请选择新发电厂的厂址，并确定各煤矿的原煤在两座发电厂之间的分配方案，使每年的总费用，即两座发电厂的运行费用与原煤运输费用之和最小。

输入格式

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

第二行包含 $m$ 个整数 $a_1,a_2,\dots,a_m$，表示各煤矿的年产量。

第三行包含 $n$ 个整数 $h_1,h_2,\dots,h_n$，表示在各备选厂址建设新发电厂时，每年的固定运行费用。

第四行包含 $m$ 个整数 $C_{10},C_{20},\dots,C_{m0}$，表示将每吨原煤从各煤矿运往现有发电厂的费用。

接下来 $n$ 行中，第 $j$ 行包含 $m$ 个整数 $C_{1j},C_{2j},\dots,C_{mj}$，表示将每吨原煤从各煤矿运往第 $j$ 个备选厂址的费用。

输出格式

第一行输出所选备选厂址的编号。如果有多个厂址均能得到最小总费用，输出编号最小的厂址。

第二行输出最小总费用。

样例输入

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

数据范围

• $n\le 50$，$m\le 5\times 10^4$，$b\le 10^4$；
• 对于所有 $1\le i\le m$，满足 $0\le a_i\le 500$；
• $a_1+a_2+\dots+a_m\ge b$；
• 对于所有 $1\le j\le n$，满足 $0\le h_j\le 100$；
• 运输费用满足 $0\le C_{ij}\le 50$。

来源与许可

本题为 HAOI 2010 试题「工厂选址」，题面与测试数据整理自 BZOJ。

样例 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