Springoalla

Springoalla는 달리기를 좋아한다. Springoalla는 $n$개의 달리기 코스를 알고 있으며, 각 코스를 달려 갔다가 다시 돌아오는 데 정확히 얼마나 걸리는지 알고 있다. 새로운 코스를 처음 달릴 때는 그 코스에 익숙해진다. 더 구체적으로 말하면, 코스의 중간 지점이 어디인지 알게 되어 그때부터는 코스의 절반을 달린 뒤 돌아올 수 있다. 그러면 달리는 시간이 절반으로 줄어든다. 예를 들어, $20$분짜리 코스의 절반을 $10$분 동안 달릴 수 있지만, 그러려면 먼저 코스 전체를 한 번 달려야 한다.

Springoalla는 너무 오래 달리지 않으면서 적어도 $t$분 동안 달리고 싶어 한다. 각 코스를 달리는 데 걸리는 시간이 주어질 때, Springoalla가 달려야 하는 최소 시간 $t_s \ge t$를 계산한다. $t_s$분 동안 달리는 방법이 여러 가지라면, 출발점에서 출발할 때마다 코스 전체를 달리든 절반을 달리든 한 번의 달리기로 셀 때, 달리기 횟수 $n_s$를 가능한 한 적게 하고 싶어 한다.

채점

제출한 해답은 여러 테스트 그룹으로 이루어진 세트에서 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$20$| $n \le 10, t \le 1000$

$2$ |$30$| Springoalla는 코스 전체만 달리면 된다.

$3$ |$50$| 추가 제약 조건이 없다.

입력의 첫 번째 줄에는 코스 수와 Springoalla가 달리고 싶은 시간을 나타내는 정수 $n$와 $t$가 주어진다(($1 \le n \le 1000$, $1 \le t \le 10^5$)). $t$가 반드시 짝수인 것은 아님에 유의한다.

두 번째 줄에는 $n$개의 정수 $l_i$가 주어지며, $2 \le l_i \le 40{,}000$는 짝수 정수로, 코스 $i$를 달리는 데 걸리는 분 수를 나타낸다.

먼저 Springoalla가 달려야 하는 시간과 총 달리기 횟수를 나타내는 정수 $t_s$와 $n_s$를 출력한다. 그다음 $n$개의 정수를 출력하며, 그중 $i$번째 정수는 코스 $i$에서 달려야 하는 시간(분)이다. $t_s$와 $n_s$가 같은 해가 여러 개라면 그중 아무거나 하나를 출력해도 된다.