g4-08751. 图书角寄书打包 · 林老师的题库

题目描述

班级图书角要给山区的小伙伴寄 $n$ 本书，第 $i$ 本书的重量为 $w_{i}$ 克。

快递站的包装袋有承重上限 $W$ 克，每条袋子最多装两本书，且袋内书的总重量不能超过 $W$ 。一本书也可以单独装一条袋子。数据保证每本书单独装袋不会超重（即 $w_{i} \leq W$ ）。

所有书都必须装袋。请编程求最少需要多少条袋子。

第一行两个整数 $n$ 和 $W$ ，用空格分隔，分别表示书的本数与每袋承重上限。

第二行 $n$ 个整数 $w_{1}, w_{2}, \dots, w_{n}$ ，用空格分隔，表示每本书的重量。

一行一个整数，表示最少需要的袋子数。

输入

8 10
9 1 2 8 5 7 3 6

输出

样例说明

一种最优装法： $(1, 9)$ 、 $(2, 8)$ 、 $(3, 7)$ 各装一袋， $5$ 和 $6$ 各自单独一袋，共 $5$ 袋。 $8$ 本书总重 $41$ 克，每袋最多装 $10$ 克，至少需要 $5$ 袋，所以 $5$ 就是最少袋数。