题目描述

一个鲜为人知的事实是，Bessie 和她的朋友们喜欢爬楼梯比赛。一个更为人知的事实是，奶牛们真的不喜欢下楼梯。因此，当奶牛们比赛到达她们最喜欢的摩天大楼的顶层后，她们遇到了一个问题。拒绝使用楼梯下楼，奶牛们被迫使用电梯返回地面层。

电梯的最大载重量为 $W$ 磅 $(1 \leq W \leq 10^8)$，奶牛 $i$ 的体重为 $C_i$ 磅 $(1 \leq C_i \leq W)$。请帮助 Bessie 找出如何用最少的电梯次数将所有 $N$ 头奶牛 $(1 \leq N \leq 18)$ 送到地面层。每次电梯的总重量不能超过 $W$。

输入格式

* 第 $1$ 行：用空格分隔的 $N$ 和 $W$。

* 第 $2$ 行到第 $N+1$ 行：第 $i+1$ 行包含一个整数 $C_i$，表示一头奶牛的体重。

输出格式

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

4 10
5
6
3
7

3

说明/提示

有四头奶牛，体重分别为 $5$、$6$、$3$ 和 $7$ 磅。电梯的最大载重量为 $10$ 磅。

我们可以将体重为 $3$ 的奶牛与其他任何一头奶牛放在同一个电梯上，但其他三头奶牛太重，无法组合在一起。对于上述解决方案，电梯行程 $1$ 包括奶牛 $1$ 和 $3$，电梯行程 $2$ 包括奶牛 $2$，电梯行程 $3$ 包括奶牛 $4$。对于此输入，还有其他几种可能的解决方案。

1 1
1

1

样例说明 #2

该组样例选自本题现有测试数据，用于展示另一种合法输入及其正确输出。

5 100
20
20
20
20
20

1

样例说明 #3

该组样例选自本题现有测试数据，用于展示另一种合法输入及其正确输出。