## 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
```

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