Problem D
2, 4, 6, Greaaat

Against her wishes, Rainbow Dash was put in charge of coach the buckball halftime cheerleading squad. While she doesn’t have the slightest care for cheerleading (she’d much rather coach the team), she’s determined to give it her all to show everypony in the squad how much she cares about them.

Figure 1: Illustration by Kyle Coate.

One of the most important things in cheerleading is regulating the crowd’s level of enthusiasm. By instructing the squad to execute different cheers, she can raise or lower this level; for example, less lively cheers temper the level of enthusiasm, while other, more exciting cheers raise it.

At the beginning, the crowd’s level of enthusiasm is zero. To prime the crowd for the second half of the game, she wants the level of enthusiasm after all the cheers to be exactly $T$. Note that it is possible for the crowd’s level of enthusiasm to dip below zero or exceed $T$ in between the cheers.

There are $N+1$ cheers at Rainbow Dash’s disposal. The $i^\text {th}$ of these cheers changes the level of enthusiasm by $S_ i$, and has a level of difficulty $D_ i$—a higher difficulty requires more practice and is harder to execute correctly. The first of these cheers is always a standard cheer with $S_1 = 1$ and $D_1 = 1$; the other $N$ non-standard cheers are possibly more complicated.

Help Rainbow Dash plan out a sequence of cheers such that the crowd’s level of enthusiasm after all the cheers is exactly $T$. Note that the same cheer can be executed multiple times, and the order of the cheers can be rearranged as necessary; moreover, the existence of the standard cheer ensures that this goal is always attainable.

Among all such sequences, she wants the total level of difficulty to be minimized in order to reduce the amount of practice the squad will need—time is of the essence and we need to make the most use of it. If a cheer appears multiple times in the sequence, its level of difficulty must be included in the total that many times.

Input

The first line of input contains two integers, $N$ ($0 \leq N \leq 500$) and $T$ ($1 \leq T \leq 200\, 000$), the number of non-standard cheers at Rainbow Dash’s disposal and the required level of enthusiasm, respectively.

The next $N$ lines of input contain the descriptions of the non-standard cheers. In particular, the $i^\text {th}$ of these lines contains two integers $S_{i+1}$ ($-T \leq S_{i+1} \leq T$) and $D_{i+1}$ ($1 \leq D_{i+1} \leq 10^9$), denoting that the $(i+1)^\text {th}$ cheer changes the level of enthusiasm by $S_{i+1}$ and has a level of difficulty of $D_{i+1}$.

Output

On the first line, output a single integer $c$, the number of cheers in the sequence.

On the second line, output $c$ integers $d_1, d_2, \dots , d_ c$ ($1 \leq d_ i \leq N+1$), denoting the cheers the squad should execute. In particular, the $i^\text {th}$ cheer the squad should execute is the ${d_ i}^\text {th}$ one. This sequence of cheers should satisfy the stipulated requirements, and, among all such sequences of cheers, have the minimum total level of difficulty.

If there are multiple correct answers, you can output any of them.

The input will be such that a solution exists with $c \leq 200\, 000$.

3 20
7 3
10 8
-2 1

5
1 2 2 2 4

4 3333
10 2
100 3
1000 4
3333 3332

12
1 1 1 2 2 2 3 3 3 4 4 4