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 ~\sum{a_i} = \sum{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 ~\left(1 \leq T \leq 10\right)~.

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)~.

Output

Với mỗi test, in ra chi phí nhỏ nhất trên một dòng.

Giới hạn

• ~1 \leq m, n \leq 200~.
• ~1 \leq a_i, b_i \leq 30000~.
• ~1 \leq C(i, j) \leq 10000~.
• ~\sum{a_i} = \sum{b_j}~.
• Kết quả nằm trong phạm vi số nguyên ~32-bit~ có dấu.

Sample 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

Sample Output

110
54