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 32-bit 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: 2014-05-12 07:24:17

ZKW is not fast enough

mssjt1: 2011-08-25 09:08:09

I can't use the ZKW's minimum cost flow to finish it!

tʰɒŋ toŋ ʨĩ: 2010-07-20 13:50:15

Khuehtsen KM soenfeah... Ngo veh ton!

Last edit: 2010-07-21 09:56:48
Serge: 2010-05-04 14:14:28

Thx.

Last edit: 2010-06-08 13:45:59
ymGXX: 2010-04-29 08:37:24

ZKW's Minimum cost flow algorithm can work it out quickly!

tracyhenry: 2010-04-05 11:43:07

Re by [Trichromatic] XilinX: Please use English to post here!

Last edit: 2010-04-06 04:53:17
Jorge Bernadas: 2009-10-09 06:56:57

I guess KM means Kühn-Munkres.

Edelweiss: 2009-09-11 02:54:30

What is "extended KM"? Could you explain it more clearly? Thanks a lot!

Edelweiss: 2009-07-24 06:26:58

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

Re: Extended KM algorithm will work.

Last edit: 2009-07-29 04:23:42

Added by:Nguyen Dinh Tu
Date:2006-01-02
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