题目描述

关于贝西和朋友们，一个鲜为人知的事实是他们喜欢爬楼梯比赛。一个更为人所知的事实是，奶牛真的不喜欢下楼梯。所以，当奶牛们跑到他们最喜欢的摩天大楼的顶部后，他们遇到了一个问题。奶牛拒绝通过楼梯爬回来，被迫使用电梯回到一楼。 电梯的最大承重能力为W（1<=W<=1000000）磅，奶牛i的重量为C_i（1<=C_i<=W）磅。请帮助Bessie找出如何使用最少次数的电梯将所有N（1<=N<=18）头奶牛送到一楼。每个电梯上奶牛的重量总和不得大于W。

输入格式

*第1行：N和W用空格分隔。 *第2..1+N行：第i+1行包含整数C_i，给出其中一头奶牛的重量。

输出格式

*单个整数R，表示所需的电梯乘坐次数的最小值。其中一个R跳下电梯。

4 10 
5 
6 
3 
7

3

提示

有四头牛，体重分别为5磅、6磅、3磅和7磅。这部电梯的最大承重能力为10磅。 我们可以把重达3磅的奶牛和其他奶牛放在同一个升降机上，但其他三头奶牛太重了，无法合并。对于上述解决方案，电梯乘坐1涉及奶牛#1和#3，电梯乘坐2涉及奶牛#2，而电梯乘坐3涉及奶牛#4。此输入可能有其他几种解决方案。