241997 - 器材箱运输

题目描述

学校要把n个器材箱送到运动场。所有器材箱都已经封好,不能拆开。第i个器材箱的重量为w_i千克。

学校准备使用同一种小推车。每辆车最多装两个器材箱,并且车上器材箱的总重量不能超过L千克。每个器材箱必须恰好装到一辆车上,一辆车也可以只装一个箱子。题目保证每个箱子的重量都不超过L。

请安排装车方案,使需要的小推车数量最少,并输出这个最少数量。不需要输出具体装车方案。

输入

第一行两个整数 n、L,表示箱子数量和每辆车的载重上限。

第二行n个整数 w_1、w_2、…、w_n,表示各箱子的重量。

【数据范围】

对全部数据,1 \le n \le 10000,1 \le L \le 10000,1 \le w_i \le L。重量相同的箱子仍然视为不同箱子。

输出

输出一个整数,表示运走全部器材箱最少需要的小推车数量。

样例

输入

5 10
2 3 7 8 9

输出

3

输入

4 8
5 5 5 5

输出

4
说明

【样例解释1】

可以把2和8装一车,3和7装一车,9单独一车,共3辆。每车最多两个箱子,5个箱子至少需要3辆,因此3辆最少。

【样例解释2】

任意两个箱子的重量和都是10,超过载重8,所以每辆车只能装一个箱子,需要4辆车。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 5
通过人数 4
金币数量 3 枚
难度 基础


上一题 下一题