← 返回题目列表

Codeforces · 1296/D

D. 与怪物战斗

中文机器翻译题面 查看原题

有$$$n$$$怪物站成一排,编号从$$$1$$$到$$$n$$$。第 $$$i$$$ 个怪物拥有 $$$h_i$$$ 生命值 (hp)。你的攻击力等于$$$a$$$ hp,而你的对手的攻击力等于$$$b$$$ hp。

你和你的对手正在与这些怪物战斗。首先,你和你的对手去找第一个怪物并战斗至死,然后你和你的对手前往第二个怪物并战斗至死,依此类推。如果怪物的生命值小于或等于 $$$0$$$,则怪物被视为死亡。

与怪物的战斗是轮流进行的。

1. 你击中怪物$$$a$$$ hp。如果你击中后它死了,你就获得一分,然后你们就可以继续处理下一个怪物。
2. 你的对手击中怪物 $$$b$$$ hp。如果他击中后怪物死了,则没有人获得分数,并且你们都将继续前往下一个怪物。

你有一些秘密技巧可以迫使你的对手跳过他的回合。您总共最多可以使用该技术 $$$k$$$ 次(例如,如果有两个怪物且 $$$k=4$$$,则您可以对第一个怪物使用该技术 $$$2$$$ 次,对第二个怪物使用 $$$1$$$ 次,但不能对第一个怪物使用 $$$2$$$ 次,对第二个怪物使用 $$$3$$$ 次)。

你的任务是确定如果你最佳地使用秘密技术,你可以获得的最大分数。

输入

输入的第一行包含四个整数 $$$n, a, b$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5, 1 \le a, b, k \le 10^9$$$) — 怪物的数量,你的攻击力,对手的攻击力和你可以使用秘术的次数。

输入的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 10^9$$$),其中 $$$h_i$$$ 是第 $$$i$$$ 个怪物的生命值。

输出

打印一个整数——如果你最佳地使用秘密技术,你可以获得的最大分数。

示例

输入 #1

6 2 3 3
7 10 50 12 1 8

输出 #1

5

输入 #2

1 1 100 99
100

输出 #2

1

输入 #3

7 4 2 1
1 3 5 4 2 7 6

输出 #3

6