\(N\) cô bò của Farmer John (\(1 \le N \le 20\)), vẫn được đánh số thuận tiện từ \(1\) đến \(N\) như thường lệ, đang chuẩn bị cho một cuộc thi mười môn phối hợp gồm \(N\) nội dung khác nhau (vì thế có lẽ nên gọi đây là cuộc thi \(N\) môn phối hợp thay vì mười môn phối hợp, vốn theo truyền thống có đúng \(10\) nội dung).

Bò \(i\) có mức kỹ năng \(s_{ij}\) (\(1 \le s_{ij} \le 1\,000\)) khi thi đấu ở nội dung \(j\). Mỗi cô bò phải thi đấu ở đúng một nội dung và mỗi nội dung phải có một cô bò tham gia.

Tổng điểm của tất cả các cô bò là tổng mức kỹ năng của họ trong những nội dung họ tham gia. Tuy nhiên, ban giám khảo cũng có thể trao điểm thưởng nếu họ đặc biệt ấn tượng. Có \(B\) khoản thưởng (\(1 \le B \le 20\)) mà ban giám khảo có thể trao. Khoản thưởng \(i\) gồm ba phần: nếu các cô bò đạt ít nhất \(P_i\) điểm (\(1 \le P_i \le 40\,000\)) trong \(K_i\) nội dung đầu tiên, tính cả các khoản thưởng khác chỉ liên quan đến những nội dung đó, họ sẽ nhận thêm \(A_i\) điểm (\(1 \le A_i \le 1\,000\)).

Ví dụ, xét \(N=3\) cô bò với các mức kỹ năng sau:

Chẳng hạn, bò \(1\) sẽ mang về cho đội \(7\) điểm nếu tham gia nội dung \(3\).

Giả sử ban giám khảo đưa ra một khoản thưởng (\(B=1\)): nếu các cô bò đạt ít nhất \(7\) điểm trong hai nội dung đầu tiên, họ sẽ nhận thêm \(6\) điểm. Khi đó, cách phân công tối ưu là xếp bò \(1\) thi nội dung \(1\), bò \(2\) thi nội dung \(3\) và bò \(3\) thi nội dung \(2\). Trong hai nội dung đầu tiên, bò \(1\) đạt \(5\) điểm và bò \(3\) đạt \(2\) điểm, tổng cộng là \(7\) điểm, đủ để nhận khoản thưởng \(1\). Do đó, tổng điểm họ đạt được là \(5+2+4+6=17\).

Hãy giúp xác định các nội dung mà những cô bò nên tham gia để tối đa hóa tổng điểm.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\) cách nhau bởi một dấu cách.
• \(B\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(K_i\), \(P_i\) và \(A_i\) cách nhau bởi dấu cách, mô tả khoản thưởng thứ \(i\).
• \(N\) dòng cuối, dòng thứ \(j\) chứa \(N\) số nguyên cách nhau bởi dấu cách là \(s_{j1},\ldots,s_{jN}\), mô tả mức kỹ năng của bò \(j\) trong từng nội dung.

Ràng buộc

• \(1 \le N \le 20\).
• \(1 \le B \le 20\).
• \(1 \le s_{ij} \le 1\,000\).
• \(1 \le P_i \le 40\,000\).
• \(1 \le A_i \le 1\,000\).

Dữ liệu ra

In ra tổng điểm lớn nhất mà các cô bò có thể nhận được, bao gồm cả điểm thưởng.

Ví dụ

3 1
2 7 6
5 1 7
2 2 4
4 2 1

17

Nguồn

USACO 2014 February Contest, Gold — Cow Decathlon

Tác giả: Lewin Gan.