题目描述

W 公司有$\red{m}$个仓库和$\red{n}$ 个零售商店。第$\red{i}$ 个仓库有$\red{a_i}$ 个单位的货物；第$\red{j}$ 个零售商店 需要$\red{b_j}$个单位的货物。货物供需平衡，即$\red{sum(a_i)=sum(b_j) }$。从第$\red{i}$ 个仓库运送每单位货物到 第$\red{j}$ 个零售商店的费用为$\red{C_{ij}}$ 。

试设计一个将仓库中所有货物运送到零售商店的运输方案， 使总运输费用最少。

编程任务： 对于给定的$\red{m}$ 个仓库和$\red{n}$ 个零售商店间运送货物的费用，计算最优运输方案和最差运输方案。

输入格式

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

输出格式

程序运行结束时，将计算出的最少运输费用和最多运输费用输出。

样例

输入样例

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

输出样例

48500
69140