题目描述

鲍茜和她的朋友们喜欢参加爬梯比赛，在这种比赛中，参与者需要爬上梯阶而不是下来。然而，没人知道的是，奶牛并不喜欢下楼梯。因此，当奶牛们完成了她们最喜欢的摩天大楼爬梯比赛之后，她们遇到了一个问题。奶牛拒绝使用楼梯下楼，所以她们只能搭乘电梯返回地面。

电梯的最大承重量为 $W$（$1 \leq W \leq 100,000,000$）磅，而第 $i$ 头奶牛的重量为 $C_i$（$1 \leq C_i \leq W$）磅。请帮助鲍茜找出如何使用最少的电梯次数将全部 $N$ 头（$1 \leq N \leq 18$）奶牛送至地面。每次乘坐电梯的奶牛重量之和必须不大于 $W$。

简易题面

给出 $n$ （$n\le 18$）个物品，体积为 $w _ 1, w _ 2, \cdots, w _ n$，现在要把它们分成若干组，要求每组的总体积小于等于 $W$（$1\le c_i\le W\le 10^8$），问最少需要多少组。

输入格式

• 第一行：用一个空格分隔的数字 $N$ 和 $W$。
• 第二行到 $1+N$ 行：第 $i+1$ 行包含一个整数 $C_i$，表示一头奶牛的重量。

输出格式

• 一个整数 $R$，表示需要的最少电梯次数。

示例

输入

4 10 
5 
6 
3 
7

输出

3

提示

这里有四头奶牛，重量分别为 $5,6,3$ 和 $7$ 磅。电梯的最大承重量为 $10$ 磅。

我们可以将重量为 $3$ 的奶牛与其他任何一头奶牛一起搭乘电梯，但是其他三头奶牛的组合重量超过了电梯的承重量。

对于以上解决方案，第一次搭乘电梯的有奶牛编号 $1$ 和 $3$，第二次是奶牛编号 $2$，第三次是奶牛编号 $4$。对于这个输入，还有许多其他的解决方案。