Một đội thợ sơn gồm ~K~ người cần thực hiện sơn một bức pano dành cho quảng cáo có dạng một hình chữ nhật kích thước ~1*N~ được chia ra làm ~N~ vạch kích thước ~1*1~. Các vạch được đánh số từ trái sang phải bắt đầu từ ~1~. Thợ ~i~ ~(1 \leq i \leq K)~ đang ngồi trước vạch ~S_{i}~ của pano và anh ta chỉ có thể sơn một dãy các vạch liên tiếp của pano trong đó phải có vạch ~S_{i}~. Thợ ~i~ chỉ có thể sơn không quá ~L_{i}~ vạch và tiền công mà anh ta nhận được từ việc sơn một vạch là ~P_{i}~. Mỗi vạch được sơn bởi không quá một thợ.
Yêu cầu: Tìm cách phân công thợ sơn các vạch của pano sao cho tổng tiền công của tất cả các thợ nhận được là lớn nhất.
Input
- Dòng đầu tiên chứa hai số nguyên dương ~N~, ~K~ ~(N \leq 16000~; ~K \leq 100)~.
- Dòng thứ ~i~ trong số ~K~ dòng tiếp theo chứa ba số nguyên ~L_{i}~, ~P_{i}~, ~S_{i}~ ~(i = 1~, ~2~, ...~K)~ được ghi cách nhau bởi dấu cách ~(1 \leq P_{i} \leq 10000~, ~1 \leq L_{i}~, ~S_{i} \leq N)~.
Chú ý:
- Cách phân công tìm được không nhất thiết phải đảm bảo sơn hết tất cả các vạch của pano.
- Nếu thợ ~i~ không sơn vạch nào cả thì việc sơn vạch ~S_{i}~ có thể được phân công cho thợ khác.
- Các số ~S_{1}~, ~S_{2}~, ...~S_{K}~ giả thiết là khác nhau từng đôi.
Output
Ghi ra tổng tiền công nhận được từ cách phân công thợ tìm được.
Sample Input
8 4
3 2 2
3 2 3
3 3 5
1 1 7
Sample Output
17
Note
(Cách phân công: Thợ ~1~ sơn các vạch ~1~, ~2~; thợ ~2~ sơn các vạch ~3~, ~4~; thợ ~3~ sơn các vạch ~5~, ~6~, ~7~; thợ ~4~ không sơn vạch nào).
Comments