链接: https://cses.fi/problemset/task/1090

板块: Sorting and Searching

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有 $n$ 个孩子想坐摩天轮，你的任务是为每个孩子安排一个座舱。

每个座舱可坐一或两名孩子，且座舱内总重量不能超过 $x$。你知道每个孩子的体重。

最少需要多少个座舱？

输入

第一行包含两个整数 $n$ 和 $x$：孩子数量和允许的最大重量。

下一行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$：每个孩子的体重。

输出

输出一个整数：最少的座舱数量。

数据范围

$1 \le n \le 2 \cdot 10^5$ $1 \le x \le 10^9$ $1 \le p_i \le x$

样例输入

4 10
7 2 3 9

样例输出

3