Elevator Optimization

A little known fact about Bessie and friends is that they love stair climbing races. A better known fact is that cows really don't like going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they have a problem. Refusing to climb back down using the stairs, the cows must use the elevator to return to the ground floor.

The elevator has a maximum weight capacity of \(W\) (\(1 \leq W \leq 100,000,000\)) pounds and cow \(i\) weighs \(C_i\) (\(1 \leq C_i \leq W\)) pounds. There are \(N\) cows (\(1 \leq N \leq 18\)).

Your task is to determine the minimum number of elevator rides required to bring all the cows to the ground floor, given that the sum of the weights on each ride does not exceed \(W\).

Input Format: The first line contains two integers \(N\) and \(W\). The second line contains \(N\) integers, where the \(i\)-th integer represents \(C_i\), the weight of the \(i\)-th cow.

Output Format: Output a single integer: the minimum number of elevator rides required.

inputFormat

The input starts with a line containing two integers \(N\) and \(W\). \(N\) is the number of cows, and \(W\) is the maximum weight capacity of the elevator.

The next line contains \(N\) space-separated integers \(C_1, C_2, \dots, C_N\), where each \(C_i\) is the weight of the \(i\)-th cow.

outputFormat

Output a single integer, which is the minimum number of elevator rides needed to get all the cows to the ground floor.

sample

4 10
5 6 3 4

2