#6011. 「网络流 24 题」运输问题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

W 公司有 m 个仓库和 n 个零售商店。第 i 个仓库有 a_i 个单位的货物;第 j 个零售商店需要 b_j 个单位的货物。货物供需平衡,即 \sum\limits_{i = 1} ^ m a_i = \sum\limits_{j = 1} ^ n b_j 。从第 i 个仓库运送每单位货物到第 j 个零售商店的费用为 c_{ij} 。试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

48500
69140

数据范围与提示

1 \leq n, m \leq 100