Submit solution
Points:
1.14 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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