Ông Kim là một địa chủ rất giàu có, sở hữu \(N\) lô đất hình vuông được xếp thẳng hàng và đánh số từ \(1\) đến \(N\). Vì các lô đất này bỏ hoang đã lâu nên lô đất nào cũng đầy cỏ dại. Để chuẩn bị cho các dự án trong tương lai và đồng thời tạo công ăn việc làm cho bà con, ông Kim quyết định tổ chức các nhiệm vụ dọn dẹp.

Ông Kim đã thông báo trên bản tin tổng cộng \(Q\) nhiệm vụ, trong đó nhiệm vụ thứ \(i\) yêu cầu dọn dẹp từ lô đất \(L_i\) đến lô đất \(R_i\) và sẽ mang lại \(S_i\) tiền thưởng nếu hoàn thành. Tuy nhiên, mỗi nhiệm vụ chỉ được thực hiện đúng một lần, và không ai được một mình dọn dẹp toàn bộ \(N\) lô đất, thế là tham lam. Nên nếu ai đó một mình dọn dẹp toàn bộ các lô đất, ông Kim sẽ thu lại hết tiền thưởng và số tiền thưởng của người đó là \(0\).

Cũng gần tới tết rồi, bạn cũng muốn kiếm chút tiền tiêu Tết mà phải không? Hãy nghĩ cách sao cho số tiền thưởng nhận được là nhiều nhất mà không bị vi phạm quy tắc của ông Kim.

Đầu vào

Dòng đầu tiên gồm hai số nguyên \(N\) và \(Q\) là số lô đất và số nhiệm vụ. \((1 \le N, Q \le 200000)\)

\(Q\) dòng tiếp theo, dòng thứ \(i\) gồm ba số nguyên \(L_i\), \(R_i\) và \(S_i\) mô tả nhiệm vụ thứ \(i\). \((1 \le L_i, R_i \le N, 0 \le S_i \le 100000)\)

Đầu ra

In ra số tiền thưởng tối đa bạn có thể nhận được.

Giới hạn

\(30\%\) số test: \(N, Q \le 18\).

\(30\%\) số test: \(N, Q \le 5000\).

\(40\%\) số test: Không có ràng buộc gì thêm.

Ví dụ

Giải thích

Ở ví dụ thứ nhất, ta sẽ thực hiện các nhiệm vụ \(1\), \(3\) và \(4\), khi đó còn hai lô đất không được dọn là \(5\) và \(8\). Tổng điểm số sẽ là \(4 + 2 + 2 = 8\).

Ở ví dụ thứ hai, ta sẽ thực hiện các nhiệm vụ \(1\) và \(2\) (hai nhiệm vụ này vẫn được xem là khác nhau). Tổng điểm số sẽ là \(5 + 5 = 10\).