摩天大楼里的奶牛(Cows in a Skyscraper)

题目描述

Bessie 和她的朋友们非常喜欢爬楼梯比赛，但奶牛们非常讨厌走下楼梯。因此，当奶牛们爬到最喜欢的摩天大楼顶层后，它们拒绝走楼梯下来，只能乘坐电梯返回一楼。

电梯的最大载重量为 $W$（$1 \le W \le 10^8$）磅，而第 $i$ 头奶牛的体重为 $C_i$（$1 \le C_i \le W$）磅。共有 $N$（$1 \le N \le 18$）头奶牛，请帮助 Bessie 计算最少需要乘坐多少趟电梯才能让所有奶牛都回到一楼。每趟电梯上所有奶牛的体重总和不得超过 $W$。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $W$。

接下来 $N$ 行，第 $i$ 行包含一个整数 $C_i$，表示第 $i$ 头奶牛的体重。

输出格式

输出一行一个整数，表示最少需要的电梯趟数。

样例输入 #1

4 10 
5 
6 
3 
7 

样例输出 #1

3 

数据范围

样例说明：共有 $4$ 头奶牛，体重分别为 $5, 6, 3, 7$ 磅，电梯最大载重 $10$ 磅。可以让 $1$ 号与 $3$ 号奶牛同乘一趟（$5 + 3 = 8 \le 10$），$2$ 号和 $4$ 号各乘一趟，共需 $3$ 趟。

对于 $100\%$ 的数据，$1 \le N \le 18$，$1 \le C_i \le W \le 10^8$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接