401685: GYM100513 J Getting Ready for VIPC

Eulampius is preparing himself to the Very Important Programming Contest (VIPC). There is a lot of time before the contest, and Eulampius hopes to make headway in his problem solving skills.

Eulampius decided to train by taking part in practice contests. He made a list of n contests that will take place before VIPC. Each contest in the list is characterized by three parameters: the day d_i of the contest, the minimum skill l_i required to take part in the contest and the maximum skill h_i that the participant can reach after taking part in the contest.

The participant skill becomes equal to h_i if he starts taking part in the contest when he's fully rested. If his fatigue equals t by the beginning of the contest, then the participant skill becomes equal to h_i - t after the contest, even if h_i - t is negative or less than his skill before the contest.

Participating in a contest takes much energy, that's why Eulampius can take part in at most one contest during a day. Participating in a contest increases Eulampius' fatigue by Δ t (same for all contests).

Each day Eulampius doesn't participate in any contest, his fatigue t becomes equal to ⌊ t / 2⌋ (divided by two rounded down).

Initially, Eulampius' skill is s, and his fatigue t equals zero. Your task is to determine the maximum skill Eulampius can reach before VIPC, no matter what his fatigue will be.

The first line contains three integers n, s, Δ t (1 ≤ n ≤ 2·10⁵,  0 ≤ s ≤ 10⁶,  0 ≤ Δ t ≤ 10⁴) — the number of contests, Eulampius' initial skill, the amount of fatigue added after a contest.

Each of the next n lines contains three integers d_i, l_i, h_i (1 ≤ d_i ≤ 10⁶, 0 ≤ l_i < h_i ≤ 10⁶) — the day of the i-th contest, the minimum skill needed to take part in the i-th contest and the maximum skill that can be reached after taking part in the i-th contest.

The contests are ordered by their dates, so d_i ≤ d_i + 1 (i = 1, 2, ..., n - 1).

In the first line print two integers c and m — the maximum skill Eulampius can reach and the number of contests he needs to take part in.

In the second line print m space-separated integers — the indices of the contests in the order of participation. The contests are indexed starting from 1 in order of their appearance in the input.

If there are multiple solutions, print any of them.

6 12 3
5 8 22
6 22 43
7 40 65
8 40 65
10 63 100
11 62 97

96 4
1 2 4 6 

4 5 3
1 5 10
2 5 15
3 15 46
4 10 42

43 2
2 3 

4 5 6
1 5 10
2 5 15
3 15 46
4 10 42

41 2
1 4 

In the first example the maximum skill that Eulampius can reach is 96:

1. Eulampius' initial skill is 12 and his fatigue is 0.
2. On the day 5 he participates in the first contest. Now his skill is 22 - 0 = 22 and his fatigue is 0 + 3 = 3.
3. On the day 6 he participates in the second contest. Now his skill is 43 - 3 = 40 and his fatigue is 3 + 3 = 6.
4. On the day 7 he does not participate in any contest. His skill is still 40 and his fatigue is .
5. On the day 8 he participates in the fourth contest. Now his skill is 65 - 3 = 62 and his fatigue is 3 + 3 = 6.
6. On the day 9 he does not participate in any contest. His skill is still 62 and his fatigue is .
7. On the day 10 he does not participate in any contest. His skill is still 62 and his fatigue is .
8. On the day 11 he participates in the sixth contest. Now his skill is 97 - 1 = 96 and his fatigue is 1 + 3 = 4.