Problem Description

Freda and rainbow raise $N(N\le 18)$ kittens. One day, the kittens are going to climb a mountain. After going through many hardships, they finally reach the top, but they are so tired that they do not want to walk down anymore.

Freda and rainbow have to pay to let them take a cable car down the mountain. Each cable car has a maximum load capacity of $W$, and the weights of the $N$ kittens are $C_1,C_2,\dots C_N$. Of course, the total weight of kittens in any cable car cannot exceed $W(1\le C_i,W \le 10^8)$. For each cable car they rent, Freda and rainbow have to pay 1 dollar, so they want to know the minimum number of dollars needed to transport all $N$ kittens down the mountain.

Input Format

The first line contains two integers $N$ and $W$, separated by a space.
The next $N$ lines each contain one integer. The integer on line $i+1$ is the weight of the $i$-th kitten, $C_i$.

Output Format

Output one integer, the minimum number of dollars needed, i.e. the minimum number of cable cars.

5 1996
1
2
1994
12
29

2

Hint

Translated by ChatGPT 5