Problem
지역간 로봇 프로그래밍 올림피아드에서는 대회가 한 라운드로 특이한 형식으로 진행됩니다. 작업은 참가자에게 순차적으로 주어지며, 모두 라운드의 맨 처음에 주어지는 것은 아니며 각 i번째 작업(1 ≤ i ≤ n)은 참가자가 s
i. 다음 작업을 받으면 각 참가자는 즉시 해결 여부를 결정해야 합니다. 그가 이 문제를 해결하기로 선택하면 확인을 위해 솔루션을 제출할 시간이 1분밖에 주어지지 않으며 이 시간 동안 다른 문제 해결로 전환할 수 없습니다. 참가자가 이 문제를 해결하기를 거부하면 앞으로 돌아갈 수 없습니다. 참가자가 해결하는 작업에 할당된 시간이 종료되는 순간, 그러한 작업이 있는 경우 동시에 사용할 수 있는 다른 작업을 해결하기 시작하거나 다른 작업이 나타날 때까지 기다릴 수 있습니다. 동시에 i번째 문제의 정답을 위해 참가자는 c
i점을 받습니다.
Interregional Olympiad에서 지역 인공 지능 센터 중 하나를 대표하는 Artur는 문제를 해결하는 능력뿐만 아니라 어떤 문제를 해결해야 하고 어떤 문제를 건너뛰어야 하는지에 대한 올바른 전략적 계산이 중요한 역할을 한다는 것을 이해합니다. 그런 올림피아드. 그는 모든 참가자와 마찬가지로 투어를 시작하기 전에 각 작업을 사용할 수 있는 시점, 솔루션에 할당되는 시간 및 해결을 위해 얻을 수 있는 포인트를 알고 있습니다. Artur는 재능 있는 학생이므로 할당된 시간 내에 Olympiad에서 해결하기로 선택한 모든 문제를 성공적으로 해결하고 검증을 통과할 수 있습니다.
아서가 풀 문제의 최적 선택으로 얻을 수 있는 최대 점수와 그러한 문제의 수와 목록을 결정하는 프로그램을 작성해야 합니다.
입력
첫 번째 줄에는 올림피아드의 문제 수인 하나의 정수 n(1 ≤ n ≤ 10
5)이 포함됩니다.
다음 n 줄에는 문제에 대한 설명이 포함되어 있으며 각 줄에 세 개의 숫자가 있습니다. 참가자가 이 문제를 해결하기 위해 받게 될 포인트(1 ≤ s
i, t
i, c
i ≤ 10
9< /sup>).
출판물
첫 줄 단일 숫자를 포함해야 합니다. – 아서가 올림피아드에서 얻을 수 있는 최대 점수입니다.
두 번째 줄에는 최적의 선택으로 해결해야 할 작업의 수인 하나의 정수 m이 포함되어야 합니다.
세 번째 줄에는 m개의 공백으로 구분된 정수가 포함되어야 합니다. 이 정수는 해결된 순서대로 문제의 번호입니다. 작업은 입력 파일에 설명된 순서대로 1부터 시작하여 번호가 매겨집니다.
최적의 답변이 여러 개인 경우 그 중 하나를 인쇄하십시오.
예
<헤드>
| # |
입력 |
출력 |
<몸>
| 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 |