Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |

## 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 8Output:110 54

Được gửi lên bởi: | Nguyen Dinh Tu |

Ngày: | 2006-01-02 |

Thời gian chạy: | 0.469s |

Giới hạn mã nguồn: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Ngôn ngữ cho phép: | Tất cả ngoại trừ: GOSU NODEJS PERL6 PYPY RUST SED VB.NET |

Nguồn bài: | Tran Quang Khai |