Bedao OI Contest 4 - OLYMPIAD

View as PDF

Submit solution


Points: 1.50 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: olympiad.inp
Output: olympiad.out

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Please read the guidelines before commenting.


There are no comments at the moment.