P13700 [NWERC 2023] Arranging Adapters

It is the day before the NWERC and you and your team are on the train towards Delft. The journey is long and boring but you came up with a good idea: "Let's do some *train*ing". $\quad$ *-- silence --*

你拿出笔记本电脑，准备插电时，发现唯一的插座已经被占用了。你的朋友们嘲笑道：“没有插座给你，我们也不训练了。”他们的笑容很快消失，因为你拿出了一个插线板，把充电器从插座上拔下来，插到了插线板上。现在，你的充电器也有地方插了。 然而，随着可用插孔的增多，你的朋友们突然又拿出了更多需要充电的设备。你意识到这样下去他们是不会训练的，于是决定用一个问题来“套路”他们。  :::align{center} 图 A.1：样例输入 2 的示意图。前六个充电器可以如图所示插入。注意，这并不是唯一的可行方案。然而，可以证明无法同时插入全部七个充电器。 ::: 你的插线板有一排 $s$ 个插孔，每个插孔直径为 $3\,\rm{cm}$。你注意到所有充电器的长度都是整数。每个充电器的插头都在两端之一，并且每个充电器只能有两种朝向。充电器之间不能重叠，但可以相互接触，并且只要插头插入插孔，充电器的其余部分可以伸出插线板的末端。具体如图 A.1 所示。 你的朋友们希望借此逃避训练，于是同意编写一个程序来解决这个问题。

输入包含两行： - 第一行包含两个整数 $n$ 和 $s$（$1\leq n\leq2\cdot 10^5$，$1\leq s\leq10^9$），分别表示你拥有的充电器数量和插线板上的插孔数量。 - 第二行包含 $n$ 个整数 $w$（$3\leq w\leq10^9$），表示每个充电器的宽度（单位为厘米）。 注意，你可以在插入前将充电器旋转 $180^\circ$。

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

由 ChatGPT 4.1 翻译