ASSIGN4  Another Assignment Problem
Assume that you are a manager and there are m types of worker (numbered from 1 to m) and n types of task (numbered from 1 to n). There are a(i) workers of type #i and b(j) postitions for task #j. C(i, j) is the cost of hiring a worker of type #i to do the task of type #j. Your job is to minimize the cost of hiring workers to fill all the positions given that the total number of workers is equal to the total number of positions.
Input
The first line of input contains the number of test cases nTest (1<= nTest <= 10). Each test case contains:
 The first line contains the number of worker types  m and number of task types  n.
 The second line contains m positive integers: a(1), a(2), ..., a(m).
 The third line contains n positive integers: b(1), b(2), ..., b(n).
 Each of the next m lines contains n integers describing matrix C(i, j).
Notes:
1 <= m, n <= 200;
1 <= a(i), b(i) <= 30000;
1 <= C(i, j) <= 10000.
Sum of a(i) equals to sum of b(j).
Output
For each test case write the minimum cost in a separate line (it will fit in a signed 32bit integer).
Example
Input: 2 3 4 3 6 7 2 5 1 8 1 2 3 4 8 7 6 5 9 12 10 11 4 4 1 3 5 7 2 4 2 8 1 4 7 3 4 7 5 3 5 7 8 3 5 3 6 8 Output: 110 54
hide comments
Yu Zhijingcheng:
20140512 07:24:17
ZKW is not fast enough 

mssjt1:
20110825 09:08:09
I can't use the ZKW's minimum cost flow to finish it! 

tÊ°É’Å‹ toÅ‹ Ê¨Ä©:
20100720 13:50:15
Khuehtsen KM soenfeah... Ngo veh ton! Last edit: 20100721 09:56:48 

Serge:
20100504 14:14:28
Thx. Last edit: 20100608 13:45:59 

ymGXX:
20100429 08:37:24
ZKW's Minimum cost flow algorithm can work it out quickly! 

tracyhenry:
20100405 11:43:07
Re by [Trichromatic] XilinX: Please use English to post here! Last edit: 20100406 04:53:17 

Jorge Bernadas:
20091009 06:56:57
I guess KM means KühnMunkres. 

Edelweiss:
20090911 02:54:30
What is "extended KM"? Could you explain it more clearly? Thanks a lot! 

Edelweiss:
20090724 06:26:58
How can we solve this problem efficiently? I don't think the minimum cost flow can work it out in 5s.

Added by:  Nguyen Dinh Tu 
Date:  20060102 
Time limit:  0.469s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  Tran Quang Khai 