Tiền khách sạn

Trong một dịp nghỉ lễ, do lượng khách du lịch đến Thành phố Phú Quốc tham quan tăng kỷ lục, dẫn đến tình trạng các khách sạn ở đây “cháy phòng”.

Khách sạn Best Western 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: Viết chương trình giúp khách sạn Best Western nhận đơn đặt phòng sao cho lợi nhuận thu được số tiền 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 một ngày.

Nhập từ bàn phím bao gồm:

• Dòng thứ nhất là số nguyên $n$ ($1 \le n \le 12000$) 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 \le 1000$, $a_i \le a_{i+1}$).

Là một số nguyên thể hiện số tiền lớn nhất.