{"raw_statement":[{"iden":"statement","content":"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. \n\nThis 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.\n\nOf 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.\n\nThe first line of the input contains two integers n and b (1 ≤ n ≤ 42, 1 ≤ b ≤ 109).\n\nThe 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.\n\nIf it's impossible to choose a suitable subset S, print \"_-1_\" (without the quotes) on a single line.\n\nOtherwise, 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.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input7 114 5005 6006 7001 2002 3003 4002 9001Output44 5 6 2Input6 56 71 22 34 55 63 4Output32 3 6"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, b \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 42 $, $ 1 \\leq b \\leq 10^9 $.  \nLet $ C = \\{ (d_i, a_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be a set of coins, where $ d_i \\in \\mathbb{Z}^+ $ is the denomination and $ a_i \\in \\mathbb{Z}^+ $ is the interestingness of coin $ i $.  \n\n**Constraints**  \nFind a subset $ S \\subseteq \\{1, \\dots, n\\} $ such that:  \n- The set $ \\{ d_i \\mid i \\in S \\} $ can represent every integer $ k \\in [1, b] $ as a subset sum.  \n- The total interestingness $ \\sum_{i \\in S} a_i $ is minimized.  \n\n**Objective**  \nMinimize $ \\sum_{i \\in S} a_i $ subject to the constraint that $ \\text{SubsetSum}( \\{ d_i \\mid i \\in S \\} ) \\supseteq [1, b] $.  \nIf no such $ S $ exists, output $-1$.  \nOtherwise, output $ |S| $ and the indices $ i \\in S $ (in any order).","simple_statement":"Baklazan has n coins. Each coin i has a value d_i and an interestingness a_i.  \nHe wants to pick a subset of coins so that he can make every amount from 1 to b using some subset of the picked coins.  \nAmong all such subsets, he wants the one with the minimum total interestingness.  \nIf impossible, print -1.  \nOtherwise, print the size of the subset, then the indices of the chosen coins.","has_page_source":false}