Có ~N~ công việc cần thực hiện, biết rằng công việc thứ ~i~ 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.

Input

Dòng đầu tiên chứa số nguyên ~N~ thoả ~ N \le 100~.

~N~ tiếp theo, dòng thứ ~i~ gồm ~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~. Dữ liệu thỏa ~1 \le a_i, t_i, c_i \le 10^6~.

Output

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 in ~4~ số: ~i, T_1, T_2, 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.

Samples

Sample Input 1

10
1 4 89
5 5 86
4 11 83
5 7 84
1 2 25
3 11 61
6 11 33
4 7 28
3 10 1
5 14 71

Sample Output 1

329
5 0 1 25
1 1 2 89
3 2 6 83
6 6 9 61
10 9 14 71