2742 - 包裹快递

题目描述

A 公司是业内有名的快递公司,不仅价格公道,快递送达的速度也非常快。之所以 A 公司有这样好的口碑,和公司“事事为客户考虑”的服务宗旨分不开。

众所周知,寄快递时,物品越多,需要的快递箱也就越多。A 公司的快递员,可以根据客户要快递的物品的体积,快速计算出最少需要几个快递箱。

今天 A 公司的快递员小明,帮客户寄快递。客户有 N 个快递要寄出,第 i 个待寄出物品的体积为 V_i,公司快递箱的体积为 MaxV,每个快递箱可以放若干个物品,只要总体积不超过 MaxV 就可以了

请问:将客户要寄出的所有快递打包走,最少需要几个快递箱。

输入

1 行输入 2 个整数 NMaxV

接下来的 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
说明

样例 1 解释

共有 5 个快递需要打包,单个快递箱的体积为 12

可以将体积为 8 和体积为 4 的物品放到第 1 个快递箱。

将体积为 6 和体积为 5 的物品放到第 2 个快递箱。

将体积为 3 的物品放到第 3 个快递箱。

这种打包方案需要 3 个快递箱。虽然这不是唯一的方案,但其他方案不会出现比使用 3 个快递箱更少的方案。

数据范围

对于 10\% 的数据,满足 1 \le N \le 5

对于 100\% 的数据满足,1 \le N \le 181 \le V_i \le MaxV1 \le MaxV \le 10^8

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 提高


上一题 下一题