Một cuộc thi có ~n~ vận động viên và ~m~ nội dung thi đấu. Các vận động viên và nội dung thi đấu được đánh số bắt đầu từ ~1~.
Thể thức thi đấu như sau:
Mỗi vận động viên ~i~ chọn đúng một nội dung ~j~ có ~c_{i, j} \ne -1~ để tham gia và đạt được ~c_{i, j}~ điểm.
Mỗi nội dung thi đấu ~j~ có tối đa ~s_j~ vận động viên được tham gia.
Tìm tổng điểm lớn nhất các vận động viên có thể đạt được.
Input
Dữ liệu vào từ file văn bản olympiad.inp:
Dòng đầu tiên gồm hai số nguyên ~n, m~ (~1 \le n \le 50000~, ~1 \le m \le 10~).
Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm ~m~ số nguyên ~c_{i, 1}, c_{i, 2}, \cdots, c_{i, m}~ (~-1 \le c_{i, j} \le 10^9~).
Dòng cuối cùng gồm ~m~ số nguyên ~s_1, s_2, \cdots, s_m~ (~1 \le s_i \le n~).
Dữ liệu đảm bảo tồn tại cấu hình thỏa mãn thể thức thi đấu.
Output
In ra file văn bản olympiad.out một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~10~ | ~m = 2~ |
2 | ~10~ | ~n \le 16~ |
3 | ~20~ | ~n \le 300~ |
4 | ~20~ | ~n \le 1000~ |
5 | ~40~ | Không có ràng buộc gì thêm |
Sample Input 1
5 3
-1 7 -1
3 5 -1
-1 6 10
-1 -1 4
2 3 -1
2 3 5
Sample Output 1
29
Notes
Ở ví dụ trên, một cách chọn tối ưu là ~[2, 2, 3, 3, 2]~. Vận động viên thứ nhất chọn nội dung ~2~, vđv thứ hai chọn nội dung ~2~, vđv thứ ba chọn nội dung ~3~, ~\cdots~. Khi đó tổng điểm tối đa là ~29~.
Comments