学校要把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
可以把2和8装一车,3和7装一车,9单独一车,共3辆。每车最多两个箱子,5个箱子至少需要3辆,因此3辆最少。
任意两个箱子的重量和都是10,超过载重8,所以每辆车只能装一个箱子,需要4辆车。