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


Submit solution

Points: 1.14 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem types

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

Comments

There are no comments at the moment.