Lập lịch hợp đồng có trọng số

Bối cảnh và bài toán

Có n hợp đồng; hợp đồng i chiếm trọn các ngày từ l_i đến r_i và mang lại lợi ích v_i. Hai hợp đồng chỉ cùng được chọn nếu hợp đồng trước kết thúc trước ngày hợp đồng sau bắt đầu.

Yêu cầu

Tối đa hóa tổng lợi ích.

Input

Dòng 1: n. Sau đó n dòng l_i r_i v_i.

Output

In tổng lợi ích lớn nhất.

Ràng buộc

• 1 <= n <= 2*10^5
• 1 <= l_i <= r_i <= 10^9
• 1 <= v_i <= 10^9

Chấm điểm

Ví dụ 1

Input

4
1 3 10
4 5 20
2 6 100
7 8 30

Output

130

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

3
1 10 5
2 3 4
4 5 4

Output

8

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.