摩天大楼

题目描述

Bessie他的奶牛朋友们，准备乘坐摩天大楼的电梯到达楼顶。但是电梯的承重有限，最大为W。但是奶牛们的重量为C_i。请帮助Bessie找出，乘最少次数的电梯，能把所有的N（1<=N<=18）头奶牛送到楼顶。

每个电梯上奶牛的重量总和不得大于W。

输入

第一行包含两个数字。分别为N和W，为奶牛的数量和电梯运行的最大承重。 之后有N行，第i行表示C_i，为第i头奶牛的重量。

输出

输出一个数字，表示需要最少次的电梯次数。

样例

提示

n\le 18,1\le c_i\le W\le 10^8

来源

USACO