Nông dân John có \(M\) cô bò, được đánh số thuận tiện từ \(1 \ldots M\), thỉnh thoảng thích đổi khẩu vị thay vì ăn cỏ. Để chiêu đãi các cô bò, Nông dân John đã nướng \(N\) chiếc bánh (\(1 \leq N \leq 300\)), được đánh số \(1 \ldots N\). Bò \(i\) thích những chiếc bánh có số trong đoạn \([l_i,r_i]\) (từ \(l_i\) đến \(r_i\), kể cả hai đầu mút), và không có hai cô bò nào thích chính xác cùng một đoạn bánh. Bò \(i\) còn có trọng lượng \(w_i\), là một số nguyên trong phạm vi \(1 \ldots 10^6\).

Nông dân John có thể chọn một dãy các cô bò \(c_1,c_2,\ldots,c_K\), sau đó những cô bò được chọn sẽ lần lượt ăn theo thứ tự đó. Thật không may, các cô bò không biết chia sẻ! Khi đến lượt bò \(c_i\) ăn, cô sẽ ăn tất cả những chiếc bánh mà mình thích — tức là tất cả bánh còn lại trong đoạn \([l_{c_i},r_{c_i}]\). Nông dân John muốn tránh tình huống khó xử khi đến lượt một cô bò ăn nhưng tất cả bánh cô thích đều đã bị ăn hết. Vì vậy, ông muốn bạn tính tổng trọng lượng lớn nhất có thể (\(w_{c_1}+w_{c_2}+\ldots+w_{c_K}\)) của một dãy \(c_1,c_2,\ldots,c_K\) sao cho mỗi cô bò trong dãy ăn được ít nhất một chiếc bánh.

Phân nhóm

• Các test 2–5 thỏa mãn \(N \leq 50\) và \(M \leq 20\).
• Các test 6–9 thỏa mãn \(N \leq 50\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \leq M \leq \frac{N(N+1)}{2}\)).

Mỗi dòng trong \(M\) dòng tiếp theo mô tả một cô bò bằng các số nguyên \(w_i\), \(l_i\) và \(r_i\).

Dữ liệu ra

In tổng trọng lượng lớn nhất có thể của một dãy hợp lệ.

Ví dụ

2 2
100 1 2
100 1 1

200

Nguồn

USACO 2019 December Contest, Platinum - Greedy Pie Eaters: https://usaco.org/index.php?page=viewproblem2&cpid=972

Tác giả: Benjamin Qi.