403360: GYM101138 H Precise Shopping

When Baklazan goes shopping, he likes calculating how much he should pay and prepare that amount exactly. There are n coins in his wallet, numbered 1 through n. Coin i has denomination d_i. Also, each coin is somewhat interesting to Baklazan; coin i has the interestingness of a_i.

This time, Baklazan forgot the first step — he doesn't know the exact amount of money to pay. He only remembers that it won't exceed b. Therefore, he'd like to prepare a subset S of his coins such that there's a subset of S with the sum of denominations equal to k for every k between 1 and b, inclusive.

Of course, it's better not to give away interesting coins. Therefore, if there are multiple ways to choose S, he'd like to minimise the sum of interestingnesses of coins in S. Note that it's not necessary to minimise the size of S.

The first line of the input contains two integers n and b (1 ≤ n ≤ 42, 1 ≤ b ≤ 10⁹).

The i-th of the next n lines contains two integers d_i and a_i (1 ≤ d_i, a_i ≤ 10⁹) — the denomination and the interestingness of the i-th coin.

If it's impossible to choose a suitable subset S, print "-1" (without the quotes) on a single line.

Otherwise, print two lines. On the first line, print one integer denoting the size of your chosen subset S. On the second line, print the space-separated indices of chosen coins. You may print the indices in any order. If there are multiple ways to choose an optimal S, you may print any of them.

7 11
4 500
5 600
6 700
1 200
2 300
3 400
2 9001

4
4 5 6 2

6 5
6 7
1 2
2 3
4 5
5 6
3 4

3
2 3 6