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

View as PDF

Submit solution

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

Problem source:
Tran Quang Khai
Problem types
Allowed languages
C, C++, Java, Pascal, Python, TEXT

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

Please read the guidelines before commenting.


There are no comments at the moment.