어댑터 배치하기

NWERC 전날, 당신과 팀원들은 델프트로 향하는 기차에 타고 있다. 여정은 길고 지루하지만 당신에게 좋은 생각이 있다. "기차에서 training 하자."

-- 침묵 --

노트북을 충전하려고 꺼냈지만 유일한 콘센트는 이미 사용 중이다. 친구들이 비웃으며 말한다. "콘센트가 없으면 training도 없다." 당신이 멀티탭을 꺼내 콘센트에서 충전기를 뽑아 멀티탭에 꽂자 비웃음이 금세 사라진다. 이제 당신의 충전기를 꽂을 자리도 생겼다.

그림 A.1: 두 번째 입력의 배치도. 처음 여섯 개의 충전기는 그림과 같이 꽂을 수 있다. 이것이 유일한 배치는 아니다. 하지만 충전기 일곱 개를 모두 꽂는 것은 불가능하다.

콘센트가 더 생기자 친구들은 충전할 기기를 더 꺼낸다. 이들이 훈련을 피하지 못하게 하려고, 대신 문제를 풀게 하기로 한다.

멀티탭에는 한 줄로 늘어선 $s$개의 콘센트가 있고, 각 콘센트의 지름은 $3 \text{cm}$이다. 모든 충전기의 길이는 정수이다. 각 충전기의 플러그는 양 끝 중 한쪽에 있고, 충전기는 두 방향 중 하나로 쓸 수 있다. 충전기끼리는 겹칠 수 없지만 맞닿는 것은 괜찮다. 플러그가 콘센트에 꽂혀 있으면 충전기는 멀티탭 끝을 넘어 튀어나와도 된다. 친구들은 동시에 꽂을 수 있는 충전기의 최대 개수를 구하는 프로그램을 작성하기로 한다.

입력은 다음과 같이 주어진다.

• 첫째 줄에 두 정수 $n$과 $s$($1\leq n\leq2\cdot 10^5$, $1\leq s\leq10^9$)가 주어진다. 충전기의 개수와 멀티탭의 콘센트 개수이다.
• 둘째 줄에 $n$개의 정수 $w$($3\leq w\leq10^9$)가 주어진다. 각 충전기의 폭(cm)이다.

꽂기 전에 충전기를 $180^\circ$ 회전해도 된다.

동시에 멀티탭에 꽂을 수 있는 충전기의 최대 개수를 출력한다.