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 begins with two positive integers $$$n$$$ $$$m$$$ ($$$n \leq 1000, m \leq n)$$$ indicating the number of warehouses and products, respectively. Following this are $$$n$$$ lines each with $$$m$$$ non-negative integers. 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 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.
Note: the bounds are actually $$$n \le 100$$$. This error was not corrected during the official contest.
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
