Transportation Problem

Problem Source

Network Flow 24 Problems

Problem Description

Company $W$ has $m$ warehouses and $n$ retail stores. Warehouse $i$ holds $a_i$ units of goods; retail store $j$ needs $b_j$ units of goods.

Supply and demand are balanced, that is $\sum\limits_{i=1}^{m} a_i = \sum\limits_{j=1}^{n} b_j$.

Shipping one unit of goods from warehouse $i$ to retail store $j$ costs $c_{ij}$.

Design a plan that ships all goods from the warehouses to the retail stores, minimizing the total shipping cost.

Input Format

The first line contains two positive integers $m, n\ (1 \le m, n \le 100)$, the number of warehouses and retail stores.

The next line contains $m$ positive integers $a_i$, the amount of goods in warehouse $i$.

The following line contains $n$ positive integers $b_j$, the amount of goods needed by retail store $j$.

The next $m$ lines each contain $n$ integers, the cost $c_{ij}\ (c_{i,j} \ge 1)$ of shipping one unit from warehouse $i$ to retail store $j$.

Output Format

Output two lines: the minimum total shipping cost and the maximum total shipping cost, respectively.

The answer is guaranteed not to exceed $10^9$.

Sample Input

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

Sample Output

48500
69140