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).