고층 빌딩의 소들

베시와 친구들에 관해 잘 알려지지 않은 사실 하나는, 이들이 계단 오르기 경주를 무척 좋아한다는 것입니다. 조금 더 잘 알려진 사실은, 소들이 계단을 내려가는 것을 정말 싫어한다는 것입니다. 그래서 소들은 가장 좋아하는 고층 빌딩 꼭대기까지 경주를 마친 뒤 곤란한 상황에 처했습니다. 계단으로 내려가기를 거부한 소들은 1층으로 돌아가기 위해 엘리베이터를 이용할 수밖에 없습니다.

엘리베이터의 최대 적재 용량은 $W$ 파운드이고, $i$번 소의 무게는 $C_i$ 파운드입니다. $N$마리의 모든 소를 가장 적은 엘리베이터 운행 횟수로 1층까지 내려보내는 방법을 구하세요. 한 번의 운행에 탑승한 소들의 무게 합은 $W$를 넘을 수 없습니다.

필요한 최소 운행 횟수만 출력하면 됩니다.

제한: $1 \le N \le 18$, $1 \le W \le 10^8$, $1 \le C_i \le W$.

• 첫 번째 줄: 두 정수 $N$과 $W$가 공백으로 구분되어 주어집니다.
• 두 번째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 한 소의 무게를 나타내는 정수 $C_i$가 주어집니다.

• 모든 소를 1층까지 내려보내는 데 필요한 최소 엘리베이터 운행 횟수를 정수 하나로 출력합니다.

예시에서는 무게가 각각 5, 6, 3, 7 파운드인 소 4마리가 있고, 엘리베이터는 최대 10 파운드까지 실을 수 있습니다. 무게가 3인 소는 다른 어느 소 한 마리와도 같이 탈 수 있지만, 나머지 세 소는 서로 짝지어 태우기에는 너무 무겁습니다. 따라서 최소 3번의 운행이 필요합니다.