Đoạn số

Là sinh viên ngành Công nghệ thông tin, Nam thường xuyên rèn luyện tư duy và kĩ năng lập trình bằng các bài toán lập trình thi đấu. Một bài toán thú vị mà Nam đang suy nghĩ để giải như sau:

Cho $n$ đoạn số nguyên trên trục số, đoạn thứ $k$ $(1\le k\le n)$ có đầu mút bên trái là $L_k$, đầu mút bên phải là $R_k$ và có trọng số là $w_k$. Với $a,b$ là hai số nguyên, trọng số của cặp số $(a,b)$ được tính bằng tổng trọng số của tất cả các đoạn $t$ mà $a\le L_t\le R_t\le b$ với $1\le t\le n$. Cần tìm cặp số nguyên $(a,b)$ có trọng số là lớn nhất.

Yêu cầu: Cho $n$ đoạn số, gọi $S$ là trọng số của cặp số nguyên $(a,b)$ có trọng số là lớn nhất, hãy giúp Nam xác định giá trị $S$.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $n$;
• Dòng thứ $k$ $(1\le k\le n)$ trong $n$ dòng tiếp theo chứa ba số nguyên $L_k,R_k,w_k$ mô tả đoạn thứ $k$ $(1\le L_k\le R_k\le {10}^6$; $|w_k|\le {10}^6)$.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên $S$ là trọng số lớn nhất xác định được.

Ràng buộc

• $1\le n\le {10}^5$.
• $1\le L_k\le R_k\le {10}^6$; $|w_k|\le {10}^6$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n\le 200$.
• Subtask 2 ($30\%$ số điểm): $n\le 2000$.
• Subtask 3 ($20\%$ số điểm): $R_1-L_1=R_2-L_2=\dots =R_n-L_n$ và $n\le {10}^5$.
• Subtask 4 ($20\%$ số điểm): $n\le {10}^5$.

Ví dụ