영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Springoalla loves to run. She knows of n running trails, and for each of them she knows exactly how long it takes her to run the trail and then back again. The first time she runs a new trail, she familiarizes herself with it. More specifically, she learns where the half-way point of the trail is, and can from then on turn back after half the trail. That halves her running time. For example, she can run half of a 20 minute trail in 10 minutes, but only after first having run 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 minutes t_s ≥ t she must run. If there are several ways to run t_s minutes, she wants to make as few runs n_s as possible, where every time she sets off from the starting point counts as one run, whether she runs a whole or a half trail.
Input
The first line of input contains the integers n and t (1 ≤ n ≤ 1000, 1 ≤ t ≤ 10^5), the number of trails and the time Springoalla wants to run. Note that t is not necessarily even.
The second line contains n integers l_i, where 2 ≤ l_i ≤ 40,000 is an even integer: the number of minutes it takes to run trail i.
Output
First output the integers t_s and n_s, the time Springoalla must run and the total number of runs she makes. Then output n integers, where the ith 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 groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | n ≤ 10, t ≤ 1000 |
| 2 | 30 | Springoalla only needs to run whole trails. |
| 3 | 50 | No additional constraints. |
예제
예제 1
3 23 10 8 14
23 3 15 8 0
예제 2
3 23 8 12 14
24 2 0 24 0
예제 3
1 3 2
3 2 3
예제 4
1 7 4
8 2 8