Problem H
Springoalla

Springoalla loves to run. She knows of $n$ running trails and knows the exact time it would take her to run the trail start to finish. The first time she runs a trail, she familiarizes herself with it. More specifically, she memorizes where in the track the half-way point is. During subsequent runs of the trail, she is able to run back after half the track. Then, she will only spend half the time in the track. For example she can run a half $20$ minute trail in $10$ minutes, but only after first running the entire trail once.

Springoalla wants to run for at least $t$ minutes without running for too long. Given the time it takes to run each trail, compute the minimum number of minute $t_ s \ge t$ she must run. If there are several ways to run $t_ s$ minutes, she wants to run as few trails $n_ s$ as possible, where each time she starts to run counts once, even if she runs a whole or half a trail.

Input

The first line of input contains the integers $n$ and $t$, where $1 \le n \le 1\, 000$ is the number of trails and $1 \le t \le 100\, 000$ is the time Springoalla wants to run. The second line contains $n$ integers $l_ i$, where $1 \le l_ i \le 40\, 000$ is an even integer: the number of minutes it takes to run trail $i$. Note that $t$ is not necessarily even.

Output

First output the integers $t_ s$ and $n_ s$, the time Springoalla must run and the number of trails. Then output $n$ integers, where the $i$’th is the number of minutes she should spend on trail $i$. If there are several solutions with the same $t_ s$ and $n_ s$ you may output any one of them.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

3 23
10 8 14

23 3
15 8 0

3 23
8 12 14

24 2
0 24 0

1 3
2

3 2
3

1 7
4

8 2
8