Bài toán 2: Cho thuê máy

Phát biểu bài toán

Trung tâm tính toán hiệu năng nhận được đơn đặt hàng của N khách hàng. Khách hàng thứ i muốn thuê máy từ ngày a_i đến ngày b_i và trả số tiền thuê là c_i.

Trung tâm chỉ có một máy cho thuê, vì vậy thời gian sử dụng máy của hai khách hàng bất kì không được giao nhau.

Hãy bố trí lịch cho thuê máy sao cho tổng số tiền thu được là lớn nhất.

Dữ liệu vào

Đọc từ file văn bản THUEMAY.INP:

• Dòng 1 ghi số nguyên dương N (1 ≤ N ≤ 10000).
• N dòng tiếp theo, dòng thứ i ghi ba số nguyên dương a_i, b_i, c_i (1 ≤ a_i, b_i ≤ 100, 1 ≤ c_i ≤ 10^9).

Trong đó:

• a_i là ngày bắt đầu thuê,
• b_i là ngày kết thúc thuê,
• c_i là số tiền khách hàng trả.

Dữ liệu ra

Ghi ra file văn bản THUEMAY.OUT:

• Một số nguyên duy nhất là tổng số tiền lớn nhất có thể thu được.

Ràng buộc

• 1 ≤ N ≤ 10000
• 1 ≤ a_i ≤ b_i ≤ 10^9
• 1 ≤ c_i ≤ 10^9

Chấm điểm

• Subtask 1 (25 điểm): 1 ≤ N ≤ 20
• Subtask 2 (35 điểm): 1 ≤ N ≤ 1000
• Subtask 3 (40 điểm): Không có ràng buộc gì thêm

Ví dụ

THUEMAY.INP

3
1 8 16
2 7 6
7 9 9

THUEMAY.OUT

16

Giải thích

Có 3 đơn thuê:

• (1, 8, 16)
• (2, 7, 6)
• (7, 9, 9)

Vì các khoảng thời gian sử dụng không được giao nhau, nên không thể chọn đồng thời đơn (1, 8, 16) với hai đơn còn lại.

Phương án tốt nhất là chọn đơn (1, 8, 16), thu được 16.