Description

你拿出笔记本电脑，准备插电时，发现唯一的插座已经被占用了。你的朋友们嘲笑道：“没有插座给你，我们也不训练了。”他们的笑容很快消失，因为你拿出了一个插线板，把充电器从插座上拔下来，插到了插线板上。现在，你的充电器也有地方插了。

然而，随着可用插孔的增多，你的朋友们突然又拿出了更多需要充电的设备。你意识到这样下去他们是不会训练的，于是决定用一个问题来“套路”他们。

:::align{center} 图 A.1：样例输入 2 的示意图。前六个充电器可以如图所示插入。注意，这并不是唯一的可行方案。然而，可以证明无法同时插入全部七个充电器。 :::

你的插线板有一排 $s$ 个插孔，每个插孔直径为 $3\,\rm{cm}$。你注意到所有充电器的长度都是整数。每个充电器的插头都在两端之一，并且每个充电器只能有两种朝向。充电器之间不能重叠，但可以相互接触，并且只要插头插入插孔，充电器的其余部分可以伸出插线板的末端。具体如图 A.1 所示。

你的朋友们希望借此逃避训练，于是同意编写一个程序来解决这个问题。

Input Format

输入包含两行：

• 第一行包含两个整数 $n$ 和 $s$（$1\leq n\leq2\cdot 10^5$，$1\leq s\leq10^9$），分别表示你拥有的充电器数量和插线板上的插孔数量。
• 第二行包含 $n$ 个整数 $w$（$3\leq w\leq10^9$），表示每个充电器的宽度（单位为厘米）。

注意，你可以在插入前将充电器旋转 $180^\circ$。

Output Format

输出你最多能同时插入插线板的充电器数量。

5 7
7 4 4 5 8

5

8 9
7 4 3 6 4 8 5 6

6

Hint

由 ChatGPT 4.1 翻译