Entertainment with Javelins

Time limit3sMemory limit512 MB

Summary

Choose a minimum-cost subset of javelins, taken in the order the machine offers them, so that their throws break through all m layers of the target.

Level: Hard9 of 10
Topics: Dynamic programming, Sorting, Simulation
Solved: No attempts yet

Problem

Sometimes the arithmetic classes are cancelled at Arithmetics University. To keep students busy during cancelled classes, the dean bought a target for throwing and a machine that sells javelins.

The target has multiple layers. Each javelin can break through several layers. The goal is to break through all layers.

Each javelin has a diameter, a strength, and a cost. The machine proposes javelins in a fixed order. For each proposed javelin, you can either buy it and throw it immediately, or discard it. Either way, the machine then proposes the next javelin. After it has proposed all javelins, it turns off.

The first thrown javelin makes a round hole with a diameter equal to its diameter and a depth equal to its strength. Each following javelin hits the center of the hole. If the diameter of the latest thrown javelin does not exceed the diameters of all previously thrown javelins, it breaks through layers starting from the first layer that has not been broken through yet. Otherwise, it breaks through layers starting from the deepest layer that has a hole with a diameter strictly less than the javelin's diameter.

Each javelin breaks through as many layers as its strength. The layers a javelin breaks through do not depend on the layers broken through by javelins with smaller diameter. If a javelin's strength is enough to break through the last layer, it passes through the target and the throwing ends.

Find the javelins to buy so that all layers are broken through at the minimum total cost.

Input

The first line contains two integers $n$ and $m$ , the number of javelins and the number of target layers ( $1 \leq n, m \leq 2000$ ).

Each of the next $n$ lines contains three integers $d_i$ , $s_i$ , and $c_i$ , the diameter, strength, and cost of the $i$ -th javelin ( $1 \leq d_i, c_i \leq 10^9$ , $1 \leq s_i \leq 2000$ ). The javelins are given in the order the machine proposes them.

Output

The first line contains two integers $c$ and $k$ , the total cost and the number of javelins in the chosen set. The second line contains $k$ integers, the identifiers of the chosen javelins in increasing order, as the machine proposes them.

If the required javelins do not exist, output $-1$ . If there are several optimal sets, output any of them.

Examples3

Example 1
Input
```
2 2
1 1 1
2 3 2
```
Expected output
```
2 1
2
```
Example 2
Input
```
2 4
1 1 1
2 3 2
```
Expected output
```
-1
```
Example 3
Input
```
2 4
1 1 1
1 3 2
```
Expected output
```
3 2
1 2
```