Thi Đấu Mười Môn

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ thí sinh và $N$ môn thi đánh số từ $1$ đến $N$ . Mỗi thí sinh $i$ có năng lực $s_{i, j}$ cho môn thi $j$ . Mỗi thí sinh tham gia đúng một môn, mỗi môn có đúng một thí sinh. Tổng điểm là tổng năng lực của các thí sinh ở môn thi họ tham gia.

Ngoài ra, có $B$ phần thưởng. Phần thưởng thứ $i$ cho $A_{i}$ điểm bổ sung nếu tổng điểm của $K_{i}$ môn thi đầu tiên (môn $1$ đến $K_{i}$ ) đạt ít nhất $P_{i}$ .

Hãy phân công thí sinh vào các môn thi sao cho tổng điểm (bao gồm cả phần thưởng) là lớn nhất.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $B$ .
$B$ dòng tiếp theo: Mỗi dòng gồm ba số nguyên $K_{i}$ , $P_{i}$ , $A_{i}$ — phần thưởng $A_{i}$ nếu tổng điểm $K_{i}$ môn đầu $\geq P_{i}$ .
$N$ dòng tiếp theo: Dòng thứ $i$ gồm $N$ số nguyên $s_{i, 1}, s_{i, 2}, \dots, s_{i, N}$ — năng lực thí sinh $i$ ở từng môn.

Dữ liệu ra

Một số nguyên duy nhất: tổng điểm lớn nhất có thể đạt được.

Ràng buộc

$1 \leq N \leq 20$
$1 \leq B \leq 20$
$1 \leq s_{i, j} \leq 1000$
$1 \leq P_{i} \leq 40000$
$1 \leq A_{i} \leq 1000$
$1 \leq K_{i} \leq N$

Ví dụ

Input	Output	Giải thích
3 1 2 7 6 5 1 7 2 2 4 4 2 1	17	Phân công: thí sinh 1 vào môn 1 (5 điểm), thí sinh 3 vào môn 2 (2 điểm), thí sinh 2 vào môn 3 (4 điểm). Tổng = $5 + 2 + 4 = 11$ . Tổng 2 môn đầu = $7 \geq 7$ nên được thưởng 6. Tổng cuối = $17$ .
3 1 1 5 1 4 4 2 5 6 2 1 1 2	12	Phân công tối ưu đạt tổng 12 bao gồm thưởng.

Bình luận

Không có bình luận tại thời điểm này.