Problem
地域間ロボットプログラミングオリンピックでは、1回戦制という珍しい形式で競技が行われます。タスクはラウンドの最初にすべてではなく、参加者に順番に与えられ、各 i 番目のタスク (1 ≤ i ≤ n) は s
i。次のタスクを受け取ったら、各参加者はそれを解決するかどうかを直ちに判断する必要があります。この問題を解決することを選択した場合、t
i 分以内にその解決策を検証のために提出する必要があり、この間、別の問題の解決に切り替えることはできません。参加者がこの問題の解決を拒否した場合、将来的にはその問題に戻ることはできません。参加者が解決しているタスクに割り当てられた時間が終了した時点で、同じ瞬間に利用可能になった別のタスク (そのようなタスクが存在する場合) の解決を開始するか、別のタスクが表示されるのを待つことができます。同時に、i 番目の問題を正しく解くと、参加者は c
i ポイントを獲得します。
地域間オリンピックの地域人工知能センターの 1 つを代表する Artur 氏は、問題を解決する能力だけでなく、どの問題を解決する必要があるか、どの問題をスキップするかについての正確な戦略的計算も重要な役割を果たすことを理解しています。そんなオリンピック。すべての参加者と同様に、彼もツアーの開始前に、各タスクがいつ利用可能になるか、その解決にどのくらいの時間が割り当てられるか、そしてそれを解決することで何ポイント獲得できるかを知っています。アルトゥールは才能のある学生なので、オリンピックで自分が解くことを選んだどんな問題も、制限時間内にうまく解決し、検証に合格することができるでしょう。
アーサーが解く問題の最適な選択とその問題の数とリストで獲得できる最大得点を決定するプログラムを書く必要があります。
入力
最初の行には、オリンピックの問題数に相当する 1 つの整数 n (1 ≤ n ≤ 10
5) が含まれています。
次の n 行には問題の説明が含まれており、各行に 3 つの数字が含まれます。si は i 番目の問題が発生した瞬間 (分単位)、t
i はその解決に割り当てられた時間 (分単位)、ci は問題の数です。この問題を解くことで参加者が受け取るポイント (1 ≤ s
i, t
i, c
i ≤ 10
9< /sup>)。
インプリント
最初の行 単一の数字を含める必要があります。アーサーがオリンピックで獲得できる最大ポイント数。
2 行目には 1 つの整数 m (最適な選択で解決されるタスクの数) が含まれている必要があります。
3 行目には、スペースで区切られた 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 |