题目描述
暑假期间,住在校园里的学生较少,因此这是代尔夫特理工大学图书馆增添新书的最佳时机。这些新书的宽度相同,但高度各异。由于现有的书柜都已经满了,图书馆管理委员会决定增加一个新的书柜来摆放这些新书。
新书柜有许多高度不一的书架。书柜的每个书架可以放 $x$ 本图书。由于可能会有一些剩余空间,管理委员会还希望在书架上摆放一些艺术品,每个书架最多摆放一件。只有当艺术品旁边最多有 $y$ 本图书时,书架上才能放得下艺术品,因为艺术品占用的空间与 $x−y$ 本图书相同。
管理委员会希望您找出最大数量的书架,既能放置艺术品,又能在书架上摆放所有新书。
输入格式
输入包括
- 一行包含四个整数 $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$ 书架,则输出可以放入的最大数量的艺术品。否则,输出 "不可能"。
样例输入 #1
4 8 4 2
4 8 6 2
1 2 3 5 7 7 8 8
样例输入 #2
4 11 3 2
2 2 2 2
1 1 1 1 1 1 1 1 1 1 1
样例输入 #3
2 10 3 2
8 6
4 2 1 3 6 2 1 3 4 5
样例输入 #4
3 8 8 3
7 9 4
2 3 4 5 6 7 8 9
提示
输入1示例说明:三个书架可以在阴影部分放置艺术品,同时还能放进所有新书。