Problem
Tại Olympic lập trình Robot liên vùng, các cuộc thi được tổ chức theo một vòng và theo thể thức khác thường. Các nhiệm vụ được giao cho những người tham gia một cách tuần tự, không phải tất cả ngay từ đầu vòng và mỗi nhiệm vụ thứ i (1 ≤ i ≤ n) sẽ có sẵn cho những người tham gia tại thời điểm s
i. Khi nhận được nhiệm vụ tiếp theo, mỗi người tham gia phải xác định ngay xem mình có giải quyết được nhiệm vụ đó hay không. Nếu anh ấy chọn giải bài toán này, thì anh ấy có t
i phút để gửi lời giải của nó để xác minh và trong thời gian này, anh ấy không thể chuyển sang giải một bài toán khác. Nếu người tham gia từ chối giải quyết vấn đề này, thì trong tương lai anh ta không thể quay lại với nó. Tại thời điểm kết thúc thời gian được phân bổ cho nhiệm vụ mà người tham gia đang giải quyết, anh ta có thể bắt đầu giải quyết một nhiệm vụ khác có sẵn cùng lúc, nếu có nhiệm vụ đó hoặc đợi một nhiệm vụ khác xuất hiện. Đồng thời, đối với giải pháp đúng của vấn đề thứ i, người tham gia nhận được c
i điểm.
Artur, người đại diện cho một trong những trung tâm trí tuệ nhân tạo của khu vực tại Olympic liên khu vực, hiểu rằng không chỉ khả năng giải quyết vấn đề mà còn là tính toán chiến lược chính xác về vấn đề nào cần giải quyết và vấn đề nào nên bỏ qua, đóng một vai trò quan trọng tại một kỳ thi Olympic như vậy. Anh ấy, giống như tất cả những người tham gia, trước khi bắt đầu chuyến tham quan, biết vào thời điểm nào mỗi nhiệm vụ sẽ có sẵn, thời gian sẽ được phân bổ cho giải pháp của nó và bạn có thể nhận được bao nhiêu điểm khi giải quyết nó. Artur là một sinh viên tài năng và do đó sẽ có thể giải thành công bất kỳ vấn đề nào anh ấy chọn để giải tại Olympic trong thời gian quy định và vượt qua để xác minh.
Yêu cầu viết một chương trình xác định số điểm tối đa mà Arthur có thể nhận được với sự lựa chọn tối ưu các bài toán mà anh ấy sẽ giải, cũng như số lượng và danh sách các bài toán đó.
Đầu vào
Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 10
5) số bài toán trong kỳ thi Olympic.
N dòng tiếp theo chứa mô tả bài toán, mỗi dòng ghi ba số: si thời điểm bài toán thứ i xuất hiện sau vài phút, t
i thời gian quy định để giải bài toán tính bằng phút và ci bao nhiêu điểm mà người tham gia sẽ nhận được khi giải quyết vấn đề này (1 ≤ s
i, t
i, c
i ≤ 10
9< /sup>).
Dấu ấn
Dòng đầu tiên phải chứa một số duy nhất – số điểm tối đa mà Arthur có thể đạt được tại Thế vận hội.
Dòng thứ hai chứa một số nguyên m - số lượng nhiệm vụ cần giải quyết với lựa chọn tối ưu.
Dòng thứ ba phải chứa m số nguyên cách nhau bởi dấu cách - số của các bài toán này theo thứ tự mà chúng đã được giải. Các nhiệm vụ được đánh số, bắt đầu từ một, theo thứ tự chúng được mô tả trong tệp đầu vào.
Nếu có một số câu trả lời tối ưu, hãy in bất kỳ câu trả lời nào trong số chúng.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
2
1 1 1
2 2 2
| 3
2
1 2
|
| 2 |
3
1 2 1
3 2 1
2 4 3
| 3
1
3 |