题目描述

有 $n$ 名学生骑双人自行车旅游，每辆双人车最多载两人，也可以只载一人，载两人时，乘客的体重之和不能超过一个给定的上限 $t$。

已知学生的体重分别为 $w_1,w_2,w_3,\dots,w_n$。请如何安排才能让所有学生骑上车且使用的车辆达到最少。

输入格式

• 第一行，两个整数：$n$ 与 $t$
• 第二行，$n$ 个整数 $w_1,w_2,\dots,w_n$

输出格式

• 单个整数，表示最少车辆数。

7 50
15 41 32 42 27 25 19

5

数据范围

• 对于 $30\%$ 的数据，$1 \leq n \leq 10$
• 对于 $60\%$ 的数据，$1 \leq n \leq 1,000$
• 对于 $100\%$ 的数据，$1 \leq n \leq 100,000$
• $1\leq w_i \leq t \leq 1,000,000$