ASSIGN4 - Lại một bài phân việc

Giới hạn
  • Thời gian: 0.469s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Có m loại nhân viên (đánh số từ 1 đến m), và có n loại việc (đánh số từ 1 đến n).

Có a(i) nhân viên loại i và b(j) công việc loại j.

Chi phí để thuê 1 nhân viên loại i làm công việc loại j là C(i, j).

Biết rằng tổng a(i) bằng tổng b(j), tìm cách thuê nhân viên để làm tất cả các công việc, sao cho tổng chi phí là nhỏ nhất.

Input

Dòng đầu: T - số lượng test (1 <= T <= 10).

Mỗi test gồm:

  • Dòng đầu: m và n
  • Dòng 2: m số a(i)
  • Dòng 3: n số b(j)
  • m dòng tiếp, mỗi dòng chứa n số, thể hiện ma trận C(i, j).

Giới hạn:

1 <= m, n <= 200;

1 <= a(i), b(i) <= 30000;

1 <= C(i, j) <= 10000.

Tổng a(i) bằng tổng b(j).

Kết quả nằm trong phạm vi số nguyên 32 bit có dấu.

Output

Với mỗi test, in ra chi phí nhỏ nhất.

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


  • Người up: dtmp
  • Nguồn bài: Tran Quang Khai