Background

There are many ways for an Agent to obtain resources, and HACK is one of them. By breaking into a Portal, you can get many useful resources.

Because the ENLIGHTENED headquarters joined the XM war, there are only a small amount of usable resources left. Therefore, the ENLIGHTENED operation commander wants to carry out HACK activities to increase the inventory as much as possible.

Problem Description

There are $n$ Portals on the map that can be HACKed, numbered from $1$ to $n$. HACKing Portal $i$ takes $t_i$ seconds and can produce $c_i$ resources to add to the inventory. However, only Portals with energy can produce resources when HACKed. For Portal $i$, its energy will be completely depleted at time $d_i$ seconds. ENLIGHTENED wants to know the maximum amount the inventory can be increased, and also output the indices of the Portals that need to be HACKed in increasing order.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain three integers $t_i$, $d_i$, $c_i$.

Output Format

The first line outputs an integer: the maximum amount the inventory can be increased.

The second line outputs an integer: how many Portals need to be HACKed.

The third line outputs the indices of the Portals to be HACKed in increasing order. If there are multiple valid HACK plans, output any one of them.

3
5 6 5
1 8 2
2 7 3

7
2
1 2

Hint

For $20\%$ of the data, $n\leq5$, $t_i\leq 5$, $c_i\leq 5$, $d_i\leq10$.

For $40\%$ of the data, $n\leq 20$, $t_i\leq 10$, $c_i\leq 10$, $d_i\leq 100$.

For $60\%$ of the data, $n\leq50$, $t_i\leq15$, $c_i\leq15$, $d_i\leq1000$.

For $100\%$ of the data, $1\leq n\leq 100$, $1 \leq t_i \leq 20$, $1\leq c_i \leq 20$, $1 \leq d_i \leq 2000$。

Translated by ChatGPT 5