A 公司是业内有名的快递公司,不仅价格公道,快递送达的速度也非常快。之所以 A 公司有这样好的口碑,和公司“事事为客户考虑”的服务宗旨分不开。
众所周知,寄快递时,物品越多,需要的快递箱也就越多。A 公司的快递员,可以根据客户要快递的物品的体积,快速计算出最少需要几个快递箱。
今天 A 公司的快递员小明,帮客户寄快递。客户有 N 个快递要寄出,第 i 个待寄出物品的体积为 V_i,公司快递箱的体积为 MaxV,每个快递箱可以放若干个物品,只要总体积不超过 MaxV 就可以了。
请问:将客户要寄出的所有快递打包走,最少需要几个快递箱。
第 1 行输入 2 个整数 N 和 MaxV 。
接下来的 N 行,每行输入一个整数,代表 N 个快递的体积。
输出一个整数,代表最少需要的快递箱的数量。
5 12 6 8 4 5 3
3
5 10 10 10 10 10 10
5
10 12 8 2 6 11 9 5 6 5 4 8
6
共有 5 个快递需要打包,单个快递箱的体积为 12。
可以将体积为 8 和体积为 4 的物品放到第 1 个快递箱。
将体积为 6 和体积为 5 的物品放到第 2 个快递箱。
将体积为 3 的物品放到第 3 个快递箱。
这种打包方案需要 3 个快递箱。虽然这不是唯一的方案,但其他方案不会出现比使用 3 个快递箱更少的方案。
对于 10\% 的数据,满足 1 \le N \le 5。
对于 100\% 的数据满足,1 \le N \le 18,1 \le V_i \le MaxV,1 \le MaxV \le 10^8。