407757: GYM102890 H How to Work Less to Pass a Programming Course in Planet E-13

H. How to Work Less to Pass a Programming Course in Planet E-13time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Planet E-13 orbits around a star in a far away galaxy named UAZ. All University students in that planet need to pass a Programming online course. For the course, the teacher assigns a set of programming problems numbered $$$1$$$ to $$$N$$$ to solve during the term. The teacher of such course is known for changing the number of problems and the number of points assigned to each problem every term, and the sum of points for all problems is not necessary the same every term, but he never assigns more than $$$20$$$ problems to solve in a term and never assign more than $$$1000$$$ points to each problem. The teacher uses a $$$0$$$ to $$$100$$$ scale for the final grade of the course and each program submitted is accepted only if it passes all the tests, for instance, if the teacher assigns $$$180$$$ points to problem number $$$10$$$, creates $$$15$$$ tests, and a student submits a solution for such problem that passes all $$$15$$$ tests, then the student receives $$$180$$$ points, but if the solution passes only $$$5$$$ of the $$$15$$$ tests, then the student receives no points at all for such program. Also, the number of points for each problem and the final grade are always integers, truncating the grade if necessary, so for instance, if the teacher assigns $$$5$$$ problems with the following points: $$$320, 170, 235, 23$$$ and $$$78$$$ (resulting in $$$826$$$ total points) and the solutions accepted for a given student are for problems $$$1, 2$$$ and $$$5$$$, the student would get $$$320+170+78=568$$$ points resulting in a grade of $$$568/826*100$$$ = 68.76 = $$$68$$$.

Thanitos is a student that will be taking the Programming Course this term and he wants to solve the minimum possible number of problems in such a way that he achieves at least a certain grade $$$G$$$, knowing that he prefers to solve the problems with lower numbers. Given a set of problems to solve, Thanitos assigns a number to the set in the following way: he starts with the number $$$0$$$, if the set contains problem $$$1$$$ then he sums $$$2^0$$$, if the set of problems to solve contains problem $$$2$$$, then he sums $$$2^1$$$, more generally, if the set contains the problem $$$i$$$, then he sums $$$2^{i-1}$$$. Two sets of problems are the same if the number assigned by Thanitos to both sets is the same. Given the number of problems the teacher will assign during the term, the minimum grade Thanitos wants to achieve and the points assigned to each problem, help Thanitos find all the different sets of problems to get at least the grade $$$G$$$ solving the minimum possible number of problems, also tell him what grade he would achieve by solving each set.

Input

The first line contains two numbers separated by a space : $$$N$$$, and $$$G$$$. Representing the number of problems assigned in the term and the minimum grade Thanitos wants to achieve in the the term. The second line will contain $$$N$$$ integer numbers $$$P_i$$$ representing the number of points assigned to each of the $$$N$$$ problems.

• $$$1 \leq N \leq 20$$$
• $$$1 \leq G \leq 100$$$
• $$$1 \leq P_i \leq 1000$$$

Output

The output consists of $$$C+1$$$ lines. The first line of the output contains two integer numbers separated by a space: $$$M, C$$$, where $$$M$$$ represents the minimum number of problems Thanitos needs to solve to achieve at least the desired grade $$$G$$$, and $$$C$$$ represents the number of combinations that would allow him to achieve at least the desired grade. Each of the following $$$C$$$ lines represents a combination of the minimum number of solved problems that would allow Thanitos to get at least the desired grade. Each of these $$$C$$$ lines include $$$M+1$$$ integers separated by a space, where the first integer $$$R$$$ represents the grade Thanitos would achieve using this combination and the remaining $$$M$$$ numbers $$$S_i$$$ represent the problem numbers that Thanitos needs to solve to get the grade $$$R$$$, where $$$S_1 < S_2 < \ldots < S_M$$$. These $$$C$$$ lines are ordered in such a way that the numbers that Thanitos would assign to each set go from the lowest possible to the highest possible. Remember that Thanitos prefers working with lower number problems so we will provide him the options ordered according to his preferences.

ExamplesInput

5 75
320 170 235 23 78

Output

3 2
87 1 2 3
76 1 3 5

Input

4 70
100 230 150 150

Output

3 3
76 1 2 3
76 1 2 4
84 2 3 4