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 \cdot n\) được chia ra làm \(n\) vạch kích thước \(1 \cdot 1\). Các vạch được đánh số từ trái sang phải bắt đầu từ \(1\). Thợ \(i\) \((1 \le i \le 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 \le 16000, k \le 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\) (\(1 \le p_i \le 10000, 1 \le l_i, s_i \le n\)) được ghi cách nhau bởi dấu cách.

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, \dots, s_k\) giả thiết là khác nhau từng đôi một.

Output

• Ghi ra tổng tiền công nhận được từ cách phân công thợ tìm được.

Example

8 4
3 2 2
3 2 3
3 3 5
1 1 7

17