Problem L
Which Warehouse?

Anaconda Inc. has a problem in several of the cities where its warehouses are located. The generic problem is the following: each city has $n$ warehouses storing $m \leq n$ different types of products distributed randomly among the warehouses (the CEO of Anaconda say the storage is not random but part of a larger master plan, but who’s kidding who here). What they want to do is consolidate the warehouses by selecting $m$ of them to each store one of the $m$ products. They could randomly select the $m$ warehouses, but even the CEO knows that’s probably not the smartest approach to this problem, since there is a cost in transferring the products to their designated new warehouses. What they want to do is to select the $m$ warehouses and assign them each a product so as to minimize the total of all the distances that the products must travel.

For example, consider this situation shown in Figure 1 (which corresponds to Sample Input 1). The figure shows three warehouses W1, W2 and W3, two products A and B, the amount of each product in each warehouse, and the distances between the warehouses. If we assign A to the W1 warehouse and B to the W2 warehouse, the total distance to move all the A’s to W1 is $0(3) + 7(5) = 35$ and the total distance to move all the B’s to W2 is $10(3)+3(3+5) = 54$ for a total cost of $89$ (note that the shortest path to move all the B’s from W3 to W2 goes through W1). However, the best solution is to assign A to W3 and B to W1 which results in a total cost of only $58$.

Figure 1: Example warehouse and product layout

Input

Input begins with two positive integers $n$ $m$ ($n \leq 100, m \leq n)$ indicating the number of warehouses and products, respectively. Following this are $n$ lines each with $m$ non-negative integers less than or equal to $1\, 000$. The $i^{th}$ value on the $j^{th}$ of these lines indicates the amount of product $i$ stored in warehouse $j$. Finally there follow $n$ lines each with $n$ integers. The $i^{th}$ value on the $j^{th}$ of these lines is either a non-negative value less than or equal to $100$ that specifies the length of the road between warehouse $j$ to warehouse $i$, or is $-1$ that indicates that there is no road directly going from warehouse $j$ to warehouse $i$. It is possible that the distance to travel on the road from one warehouse $r$ to another warehouse $s$ may not be the same as the distance to travel on the road from $s$ to $r$. The distance from any warehouse to itself is always 0 and there is always at least one path between any two warehouses.

Output

Output the minimum distance to move all the products using the optimal assignment of products to warehouses.

3 2
5 10
0 6
7 3
0 3 5
3 0 9
5 9 0

58

3 2
5 10
0 6
7 3
0 -1 5
-1 0 9
5 9 0

124