Sau trận thua ~0-1~ muối mặt trước ĐTQG Indonesia trong khuôn khổ ASIAN CUP 2023. HLV Philippe Troussier đã quyết định sẽ gặp mặt riêng với các cầu thủ nhầm nói chuyện khích lệ động viên tinh thần. Được biết HLV sẽ nói chuyện với một cầu thủ cùng lúc.
Biết rằng ĐTQG Việt Nam có ~n~ cầu thủ, để nói chuyện với cầu thủ thứ ~i~ thì HLV sẽ cần dành ra khoảng thời gian ~[l_i, r_i)~ và lượng hào khí tăng thêm sẽ là ~c_i~ (lưu ý rằng ~c_i~ có thể âm vì có một vài cầu thủ hướng nội).
Bạn hãy giúp HLV Philippe Troussier tìm cách xếp lịch nói chuyện để hào khí của đội tuyển đạt cao nhất nhé.
Input
Dòng đầu tiên chứa một số nguyên dương ~n~ là số cầu thủ của ĐTQG Việt Nam.
~n~ dòng tiếp theo, mỗi dòng chứa ba số là ~l_i, r_i, c_i~ tương ứng.
Output
Đưa ra một số duy nhất là lượng hào khí tăng lên tối đa của đội tuyển.
Constraint
- ~n \leq 5000~.
- ~1 \leq l_i < r_i \leq 10^9~.
- ~|c_i| \leq 10^5~.
Subtask
- Subtask 1 (25%): ~n \leq 20~.
- Subtask 2 (75%): không có giới hạn gì thêm.
Sample Input
3
1 3 5
1 2 1
2 3 5
Sample Output
6
Notes
HLV sẽ họp bàn với cầu thủ thứ hai và sau đó cầu thủ thứ ba, lượng hào khí tăng thêm là ~1 + 5 = 6~.
Bình luận