本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1170. 运输问题


Description

W 公司有 m 个仓库和 n 个零售商店。第 i 个仓库有 ai 个单位的货物;第 j 个零售商店需要 bj 个单位的货物。货物供需平衡,即 a1+a2+...+am=b1+b2+...+bn。从第 i 个仓库运送每单位货物到第 j 个零售商店的费用为 cij。试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。

Input

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

Output

两行分别输出最小运输费用和最大运输费用。

Samples

Input Copy
2 3
220 280
170 120 210
77 39 105
150 186 122
Output
48500
69140

Hint

n,m<=100

Source

网络流24题
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 256MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1021. 网络流训练2
My history solutions

You didn't submit any solution!
Submit your solution

Login Register