Minimum Cable Cars Required

Freda and Rainbow have N kittens (with N ≤ 18) that they need to transport down a mountain using cable cars. Each cable car has a maximum weight capacity of \(W\) and the kittens weigh \(C_1, C_2, \ldots, C_N\). The sum of the weights of the kittens in any one cable car cannot exceed \(W\). Each cable car rental costs 1 dollar. Determine the minimum amount of money (i.e. the minimum number of cable cars) needed to transport all of the kittens down the mountain.

Note: The input weights and capacity are positive integers with \(1 \leq C_i, W \leq 10^8\). The problem can be solved using dynamic programming with bitmask since N is small.

inputFormat

The first line contains two integers, N and W, representing the number of kittens and the maximum weight capacity of each cable car respectively.

The second line contains N integers: \(C_1, C_2, \ldots, C_N\), separated by spaces, indicating the weights of the kittens.

outputFormat

Output a single integer: the minimum number of cable cars needed to transport all of the kittens down the mountain.

sample

3 10
5 6 3

2