Minimum Transportation Cost

Company \(W\) has \(m\) warehouses and \(n\) retail stores. The \(i\)-th warehouse has \(a_i\) units of goods, and the \(j\)-th retail store requires \(b_j\) units of goods. It is guaranteed that the total supply equals the total demand, i.e., \(\sum_{i=1}^{m}a_i = \sum_{j=1}^{n}b_j\).

The cost to transport one unit of goods from the \(i\)-th warehouse to the \(j\)-th retail store is given by \(c_{ij}\). Your task is to design a transportation plan to ship all goods from the warehouses to the retail stores such that the total transportation cost is minimized.

inputFormat

The first line contains two integers \(m\) and \(n\) representing the number of warehouses and retail stores respectively.

The second line contains \(m\) integers \(a_1, a_2, \ldots, a_m\) denoting the supply of each warehouse.

The third line contains \(n\) integers \(b_1, b_2, \ldots, b_n\) denoting the demand of each retail store.

This is followed by \(m\) lines, each containing \(n\) integers. The \(j\)-th integer of the \(i\)-th line represents \(c_{ij}\), the cost to ship one unit of goods from the \(i\)-th warehouse to the \(j\)-th retail store.

outputFormat

Output a single integer representing the minimum total transportation cost.

sample

2 2
5 5
6 4
1 2
3 1

12