运输问题

Description

W 公司有 m 个仓库和 n 个零售商店。第 i 个仓库有ai$a_i$个单位的货物；第 j 个零售商店需要bj$b_j$个单位的货物。货物供需平衡，即Σai=Σbj $$/Sigma a_i = /Sigma b_j$$ 从第 i 个仓库运送每单位货物到第 j 个零售商店的费用为cij$c_{ij}$。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。 对于给定的 m 个仓库和 n 个零售商店间运送货物的费用，计算最优运输方案和最差运输方案。

Input

第 1 行有 2 个正整数 m和 n，分别表示仓库数和零售商店数。接下来的一行中有 m个正整数ai$a_i$，1≤i≤m，表示第 i 个仓库有ai$a_i$个单位的货物。再接下来的一行中有 n 个正整数bj$b_j$，1≤j≤n，表示第 j 个零售商店需要bj$b_j$个单位的货物。接下来的 m行，每行有 n 个整数，表示从第 i 个仓库运送每单位货物到第 j 个零售商店的费用cij$c_{ij}$ 。

Output

输出计算出的最少运输费用和最多运输费用。

Sample Input

2 3 220 280 170 120 210 77 39 105 150 186 122

Sample Output

48500 69140

题解

建图： 建立附加源S，附加汇T。 1.S向每个仓库连接一条容量为仓库货物数量，费用为0的边。 2.每个商店向T连接一条容量为商店需要货物数量，费用为0的边。 3.每个仓库和每个商店之间连接一条容量无穷大，费用为运送费用的边。 求出最小(大)费用最大流就是答案。