Người Ăn Bánh

Có $N$ chiếc bánh đặt tại các vị trí $1,2,\dots ,N$ trên một hàng thẳng, và $M$ người ăn bánh. Người thứ $i$ có trọng số $w_i$ và thích ăn bánh trong đoạn $[l_i,r_i]$ — tức là người này sẽ ăn đúng một chiếc bánh nằm trong khoảng từ $l_i$ đến $r_i$.

Mỗi chiếc bánh chỉ có thể được ăn bởi tối đa một người. Hãy chọn một tập con các người và phân công mỗi người trong tập đó ăn một chiếc bánh (không có hai người cùng ăn một chiếc), sao cho tổng trọng số của những người được chọn là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $M$ ($1\le N\le 300$, $1\le M\le N(N+1)/2$).
• $M$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $w_i$, $l_i$, $r_i$ ($1\le l_i\le r_i\le N$, $1\le w_i\le {10}^6$).

Dữ liệu ra

Một số nguyên duy nhất — tổng trọng số lớn nhất có thể.

Ví dụ