2142. 放书

单点时限: 2.0 sec

内存限制: 256 MB

你要把一叠书放进一些箱子里面,为了节约箱子,你要放尽量多的书到一个箱子里面,但不能超过箱子的重量限制。

当你把尽量多的书放进一个箱子以后,你把箱子关上,然后用下一个箱子去装书。为了避免麻烦,你只按书堆叠的从上到下的顺序把书放进箱子,也就是说在下面的书不会比上面的书先放进箱子。

从上到下给你每本书的重量和箱子的能承受的重量,你能求出需要多少个箱子吗?

输入格式

第一行是一个整数 T, 表示有 T 组测试数据。

每组测试数据的第一行是两个整数 n(0<=n<=50),k(1<=k<=1000),表示有 n 本书,每个箱子的载重上限是 k。

接下来一行有 n 个整数,表示 n 本书的重量,从上到下。这 n 个整数都大于等于 1 且小于等于 k。

输出格式

对于每组测试数据,输出需要箱子的个数,占一行。

样例

Input
2
6 10
5 5 5 5 5 5
11 12
12 1 11 2 10 3 4 5 6 6 1
Output
3
6

152 人解决,195 人已尝试。

178 份提交通过,共有 479 份提交。

2.9 EMB 奖励。

创建: 12 年,4 月前.

修改: 3 年,2 月前.

最后提交: 4 天,4 小时前.

来源: 第一届程序设计竞赛热身赛

题目标签
dfs