403360: GYM101138 H Precise Shopping

Memory Limit:512 MB Time Limit:6 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Precise Shoppingtime limit per test6 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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 di. Also, each coin is somewhat interesting to Baklazan; coin i has the interestingness of ai.

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.

Input

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

The i-th of the next n lines contains two integers di and ai (1 ≤ di, ai ≤ 109) — the denomination and the interestingness of the i-th coin.

Output

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.

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

加入题单

上一题 下一题 算法标签: