P13750 [NWERC 2024] Limited Library

在暑假期间，校园里居住的学生较少，因此这是为代尔夫特理工大学图书馆增添新书的绝佳时机。这些新书的宽度都相同，但高度各不相同。由于现有的书架都已满，图书馆管理委员会决定新增一个书架来展示这些新书。 :::align{center}  代尔夫特理工大学图书馆的众多书架。 ::: 新书架有若干层，每层高度不同。每层最多可放 $x$ 本书。由于可能会有剩余空间，管理委员会还希望在书架上展示一些艺术品，每层最多放一个艺术品。只有当该层旁边最多有 $y$ 本书时，艺术品才能放下，因为艺术品占据与 $x-y$ 本书相同的空间。例如，图 L.1 展示了一个书架，其中有三层可以放置艺术品。 :::align{center}  图 L.1：样例输入 1 的示意图。三层可以在阴影区域放置艺术品，同时还能放下所有新书。 ::: 管理委员会希望你找出，在能够放下所有新书的前提下，最多能在多少层上放置艺术品。

输入包括： - 一行四个整数 $n$、$m$、$x$、$y$（$1 \leq n, m \leq 10^5$，$1 \leq y < x \leq 1000$），分别表示书架的层数、新书的数量、每层最多可放的书本数、每层与艺术品并排时最多可放的书本数。 - 一行 $n$ 个整数 $a$（$1 \leq a \leq 10^9$），表示每层的高度。 - 一行 $m$ 个整数 $b$（$1 \leq b \leq 10^9$），表示每本书的高度。

如果能将 $m$ 本书全部放入 $n$ 层书架中，输出最多能放置的艺术品数量。否则，输出“$\texttt{impossible}$”。

由 ChatGPT 4.1 翻译