Đà Lạt là một thành phố du lịch đầy thơ mộng. Vào các dịp lễ hoặc kỳ nghỉ dài thành phố này luôn đón một lượng khách du lịch lớn vì thế các khách sạn luôn trong tình trạng cháy phòng. Khách sạn Mộng Mơ chỉ còn một phòng nên quyết định cho thuê phòng này theo hình thức thỏa thuận về giá cả. Sau khi tổng hợp các đơn đặt hàng, khách sạn nhận được ~n~ đơn đặt hàng, trong đó đơn đặt hàng thứ ~i~ đăng ký ngày bắt đầu là ~a_i~, ngày trả phòng là ~b_i~ và chấp nhận trả số tiền thuê phòng là ~c_i~. Do có nhiều đơn đặt hàng, thời gian đặt phòng lại chồng chéo nhau, số tiền khách hàng chấp nhận trả cho khách sạn cũng khác nhau nên ban quản lý khách sạn đang rất khó khăn không biết nhận lời hay từ chối khách hàng nào.
Yêu cầu: Em hãy viết chương trình giúp khách sạn nhận đơn đặt phòng sao cho lợi nhuận thu được là lớn nhất.
Lưu ý: Theo điều lệ của khách sạn, khách hàng phải trả phòng trước ~12~ giờ trưa, khách hàng khác có thể nhận phòng từ ~12~ giờ trong ngày.
Dữ liệu vào
- Số nguyên ~n~ (~1 \le n \le 10000~) thể hiện số đơn đặt hàng
- ~n~ dòng tiếp theo gồm ~3~ số nguyên ~a_i~, ~b_i~ và ~c_i~. Mỗi số cách nhau một khoảng trắng. (~1 \le a_i \le b_i \le 100~, ~0 \le c_i \le 1000~).
Dữ liệu ra
- Một số nguyên thể hiện số tiền lớn nhất mà khách sạn có thể thu được.
Ví dụ 1
Dữ liệu vào
3
1 2 8
2 3 6
4 7 6
Dữ liệu ra
20
Ví dụ 2
Dữ liệu vào
4
1 4 5
1 3 8
3 5 4
4 6 9
Dữ liệu ra
17
Ràng buộc
Subtask ~1~ (~30\%~): ~1 \le n \le 10~, ~1 \le a_i \le b_i \le 10~, ~0 \le c_i \le 10~.
Subtask ~2~ (~30\%~): ~1 \le n \le 1000~, ~1 \le a_i \le b_i \le 50~, ~0 \le c_i \le 100~.
Subtask ~3~ (~20\%~): ~1 \le n \le 5000~, ~1 \le a_i \le b_i \le 50~, ~0 \le c_i \le 500~.
Subtask ~4~ (~20\%~): ~1 \le n \le 10000~, ~1 \le a_i \le b_i \le 100~, ~0 \le c_i \le 1000~.
Comments