题目描述

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

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

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

输入格式

第 ${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}$。对于这个输入，其他几种解决方案也是可能的。