C1410 [HAOI2010]工厂选址

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

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

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

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

样例输出 1

8
49