Description

Company $W$ has $m$ warehouses and $n$ retail stores. The $i$-th warehouse has $a_i$ units of goods; the $j$-th retail store needs $b_j$ units of goods.

The supply and demand are balanced, i.e., $\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$.

The cost to transport each unit of goods from the $i$-th warehouse to the $j$-th retail store is $c_{i,j}$.

Design a transportation plan to ship all goods from the warehouses to the retail stores so that the total transportation cost is minimized.

Input Format

Line 1 contains 2 positive integers $m$ and $n$, representing the number of warehouses and retail stores, respectively.

The next line contains $m$ positive integers $a_i$, where the $i$-th warehouse has $a_i$ units of goods.

The following line contains $n$ positive integers $b_j$, where the $j$-th retail store requires $b_j$ units of goods.

The next $m$ lines each contain $n$ integers, representing the per-unit transportation cost $c_{i,j}$ from the $i$-th warehouse to the $j$-th retail store.

Output Format

Output two lines: the minimum total transportation cost and the maximum total transportation cost.

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

48500
69140

Hint

$1 \leq n, m \leq 100$.

Translated by ChatGPT 5