题目描述

关于 $\red{Bessie }$和朋友的一个鲜为人知的事实是，他们喜欢爬楼梯比赛。一个更广为人知的事实是奶牛真的不喜欢下楼梯。所以在奶牛们跑到他们最喜欢的摩天大楼的顶部之后，他们遇到了问题。拒绝使用楼 梯爬下来，奶牛被迫使用电梯回到底层。

电梯的最大重量容量为 $\red{W (1 <= W <= 100,000,000) }$磅，奶牛 $\red{i }$的重量为 $\red{C_i (1 <= C_i <= W) }$磅。请帮助 $\red{Bessie }$弄清楚如何使用最少的电梯次数将所有 $\red{N (1 <= N <= 18) }$头奶牛送到一楼。每次乘坐电梯时奶牛的重量总和不得大于 $\red{W}$。

给出$\red{n}$个物品，体积为$\red{w[i]，}$现把其分成若干组，要求每组总体积$\red{<=W，}$问最小分组。$\red{(n<=18)}$

输入格式

第 $\red{1 }$行：$\red{N }$和 $\red{W }$用空格分隔。

第 $\red{2..1+N }$行：第 $\red{i+1 }$行包含整数 $\red{C_i，}$给出其中一头奶牛的重量。

输出格式

一个整数 $\red{R，}$表示需要乘坐电梯的最少次数。

其中一个 $\red{R }$下电梯。

样例

输入样例

4 10 
5 
6 
3 
7

输出样例

3

提示

有四头奶牛，体重分别为 $\red{5}$、$\red{6}$、$\red{3 }$和 $\red{7 }$磅。电梯的最大承重能力为 $\red{10 }$磅。

我们可以将重 $\red{3 }$的母牛与其他任何母牛放在同一个电梯上，但其他三头母牛太重而无法组合。对于上述解决方案，乘坐电梯 $\red{1 }$涉及奶牛 #$\red{1 }$和 #$\red{3，}$乘坐电梯 $\red{2 }$涉及奶 牛 #$\red{2，}$乘坐电梯 $\red{3 }$涉及奶牛 #$\red{4}$。对于这个输入，其他几种解决方案也是可能的。