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 $nn$ warehouses storing $m\le nm\; \backslash 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 $mm$ of them to each store one of the $mm$ products. They could randomly select the $mm$ 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 $mm$ 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 L.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)=350(3)\; +\; 7(5)\; =\; 35$ and the total distance to move all the B's to W2 is $10(3)+3(3+5)=5410(3)+3(3+5)\; =\; 54$ for a total cost of $8989$ (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 $5858$.

Figure L.1: Example warehouse and product layout

입력

Input begins with two positive integers $nn$ $mm$ ($n\le 100n\; \backslash leq\; 100$, $m\le nm\; \backslash leq\; n$) indicating the number of warehouses and products, respectively. Following this are $nn$ lines each with $mm$ non-negative integers less than or equal to 1000. The $ii$^th value on the $jj$^th of these lines indicates the amount of product $ii$ stored in warehouse $jj$. Finally there follow $nn$ lines each with $nn$ integers. The $ii$^th value on the $jj$^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 $jj$ to warehouse $ii$, or is $-1-1$ that indicates that there is no road directly going from warehouse $jj$ to warehouse $ii$. It is possible that the distance to travel on the road from one warehouse $rr$ to another warehouse $ss$ may not be the same as the distance to travel on the road from $ss$ to $rr$. The distance from any warehouse to itself is always 0 and there is always at least one path between any two warehouses.

출력

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