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

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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