题目描述

Freda 和 rainbow 饲养了 N 只小猫。这天，小猫们要去爬山。小猫们爬上山顶后太累了，不想徒步下山，于是需要坐索道。

索道上的缆车最大承重量为 W，N 只小猫的重量分别是 C_1,C_2,...,C_N。每辆缆车上的小猫重量之和不能超过 W。每租用一辆缆车需要 1 美元，求最少需要多少辆缆车。

输入格式

第一行两个整数 N,W。

接下来 N 行，每行一个整数，表示一只小猫的重量。

输出格式

一行一个整数，表示最少需要的缆车数量。

样例输入 #1

5 1996
1
2
1994
12
29

样例输出 #1

2

数据范围与提示

1 <= N <= 18，1 <= C_i,W <= 100000000。

本题适合练习 DFS、回溯和剪枝。通常先将小猫重量从大到小排序，再搜索每只小猫放入已有缆车或新开缆车。

来源

洛谷 P10483 小猫爬山。