Bài 4: (3 điểm) Thuê máy                       

Tại thời điểm 0, ông chủ cho thuê máy tính nhận được đơn đặt hàng thuê sử dụng của N khách. Các khách hàng được đánh số từ 1 đến N. Khách hàng i cần sử dụng máy từ thời điểm d_i đến thời điểm C_i (D_i và C_i là các số nguyên và 0<D_i<C_i<10¹⁰), và sẽ trả tiền sử dụng máy là P_i (P_i nguyên và 0<P_i<10⁸);

Yêu cầu: Hãy xác định xem ông chủ cần nhận phục vụ những khách hàng nào sao cho khoảng thời gian sử dụng máy tính của hai khách hàng được nhận phục vụ bất kì không giao nhau và tổng tiền thu được từ phục vụ là lớn nhất.

Dữ liệu vào: vào file văn bản BAI4.INP.

• Dòng đầu ghi số N (0<N<=1000).
• Dòng thứ i trong N dòng tiếp theo ghi 3 số D_i, C_i, P_i cách nhau bởi dấu cách, i=1,2,..,N