Đợt thi kết thúc học phần sắp tới, Trung tâm Khảo thí công bố ~n~ ca coi thi còn thiếu cán bộ, đánh số từ ~1~ đến ~n~. Ca thứ ~i~ bắt đầu tại thời điểm ~s_i~, kết thúc tại thời điểm ~e_i~ (các số nguyên, tính theo cùng một đơn vị thời gian) và được trả thù lao ~w_i~ nghìn đồng. Người coi thi phải có mặt trong suốt nửa khoảng ~[s_i, e_i)~.

Thầy Minh muốn đăng ký một số ca nhưng không thể coi hai ca giao nhau về thời gian. Hai ca ~i~ và ~j~ không giao nhau khi và chỉ khi ~e_i \le s_j~ hoặc ~e_j \le s_i~; nói riêng, nếu ca này kết thúc đúng lúc ca kia bắt đầu thì thầy vẫn nhận được cả hai.

Yêu cầu

Hãy chọn một tập các ca đôi một không giao nhau có tổng thù lao lớn nhất và in ra tổng đó.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~n~;
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ba số nguyên ~s_i~, ~e_i~ và ~w_i~ mô tả ca thứ ~i~. Các ca được cho theo thứ tự bất kỳ; có thể có nhiều ca trùng nhau về thời gian.

Kết quả ra

Ghi ra một số nguyên duy nhất là tổng thù lao lớn nhất (nghìn đồng).

Ràng buộc

~1 \le n \le 2 \cdot 10^5~; ~0 \le s_i < e_i \le 10^9~; ~1 \le w_i \le 10^9~.

• Subtask 1 (15% số điểm – test 01–03): ~n \le 15~;
• Subtask 2 (25% số điểm – test 04–08): ~n \le 3000~;
• Subtask 3 (20% số điểm – test 09–12): mọi ~w_i = 1~;
• Subtask 4 (40% số điểm – test 13–20): không có ràng buộc bổ sung.

Lưu ý: kết quả có thể vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

5
11 16 9
15 16 2
9 13 8
7 9 2
13 17 8

Kết quả ra mẫu 1

18

Giải thích

Phương án tốt nhất là nhận các ca ~4~, ~3~ và ~5~, ứng với các nửa khoảng ~[7, 9)~, ~[9, 13)~ và ~[13, 17)~: ca trước kết thúc đúng lúc ca sau bắt đầu nên hợp lệ, tổng thù lao là ~2 + 8 + 8 = 18~. Ca ~1~ có thù lao cao nhất nhưng giao với cả ca ~3~ lẫn ca ~5~: nhận ca ~1~ thì chỉ thêm được ca ~4~, tổng là ~11~.