Có N công việc cần thực hiện. Biết rằng công việc thứ i (i=1,2,..,N) nếu được thực hiện xong trước thời hạn t_i thì sẽ thu được tiền công là c_i. Để thực hiện công việc i cần a_i đơn vị thời gian. Tại mỗi thời điểm chỉ có thể thực hiện được 1 công việc, thời gian chuyển thực hiện công việc xem như không đáng kể.

Hãy xếp lịch thực hiện các công việc sao cho thu được nhiều tiền thù lao nhất.

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

• Dòng đầu tiên ghi số nguyên N (N£100)
• N dòng sau, dòng thứ i ghi 3 số a_i, t_i, c_i tương ứng là thời gian cần thiết để thực hiện, thời điểm bắt buộc phải xong và tiền công thu được của công việc i

Kết quả: Ghi ra file văn bản XepLich.OUT

• Dòng đầu tiên ghi tổng giá trị tiền công thu được
• Các dòng tiếp theo, mỗi dòng ghi 4 số: i, T₁, T₂, gt tương ứng là số hiệu, thời điểm bắt đầu, thời đểm kết thúc và giá trị thu được của công việc được chọn. Các công việc được liệt kê theo thứ tự thực hiện.