C. Space Expedition
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

A space explorer plans to go on an expedition to a remote planet. In his path, there are several space objects given in order of visiting them, each of which has its own unique value for exploration. Each object requires a certain amount of energy (in units) and time (in days) for the study.

However, the explorer has a limitation on the amount of available energy $$$K$$$ and time $$$M$$$ to complete the mission. It is necessary to create an optimal sequence of visiting objects that maximizes the scientific value of the expedition, taking into account the constraints on energy and time.

Input

The first line contains three space-separated integers: the number of space objects $$$1 \le N \le 100$$$ and the limitations on energy $$$1 \le K \le 100$$$ and time $$$1 \le M \le 100$$$.

Each of the next $$$N$$$ lines described an object and contains three integers: its scientific value $$$0 \le V \le 150$$$, the amount of energy $$$1 \le F \le 50$$$ required, and the time in days $$$1 \le T \le 20$$$ needed for exploration.

Output

The first line should contain a number: the maximum scientific value of the exploration. The second line should contain the sequence of visiting objects.

It is assumed that the objects are numbered sequentially, starting from one. The explorer can only visit them in the specified order.

If it is not possible to explore any object, output 0.

If there are several possible solutions, output any one of them.

Examples
Input
5 60 10
100 20 3
80 17 2
50 10 4
120 25 4
60 12 2
Output
280
1 4 5
Input
2 12 10
67 15 9
120 4 15
Output
0
Input
4 40 30
30 7 10
50 16 12
80 12 20
15 5 7
Output
110
1 3