Phân Bổ Ca Trực Bác Sĩ Nội Trú
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Một bệnh viện có $N$ bác sĩ nội trú và $M$ ngày trực chuyên môn. Bác sĩ thứ $i$ chỉ có thể trực tối đa $L_i$ ngày trong đợt này. Ngày thứ $j$ cần đúng $R_j$ bác sĩ trực. Nếu bác sĩ $i$ nhận trực vào ngày $j$, bệnh viện cần chi trả mức phụ cấp $W_{i,j}$ (nếu $W_{i,j} = -1$ nghĩa là bác sĩ $i$ bận lịch mổ vào ngày $j$). Hãy tính tổng phụ cấp nhỏ nhất để xếp đủ người cho tất cả $M$ ngày trực.
Dữ liệu vào
Dòng 1 gồm hai số nguyên $N, M$ ($1 \le N, M \le 30$). Dòng 2 gồm $N$ số nguyên $L_i$ ($0 \le L_i \le M$). Dòng 3 gồm $M$ số nguyên $R_j$ ($0 \le R_j \le N$). $N$ dòng tiếp theo, mỗi dòng gồm $M$ số nguyên $W_{i,j}$ ($-1 \le W_{i,j} \le 1000$).
Dữ liệu ra
In ra tổng phụ cấp nhỏ nhất, hoặc -1 nếu không thể xếp đủ lịch trực.
Ví dụ
| Input | Output |
|---|---|
| 3 3 2 2 2 2 1 2 3 4 2 5 1 3 2 6 4 |
11 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion