Thi Đấu Mười Môn

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 $\ge 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\le N\le 20$
• $1\le B\le 20$
• $1\le s_{i,j}\le 1000$
• $1\le P_i\le 40000$
• $1\le A_i\le 1000$
• $1\le K_i\le N$

Ví dụ