406780: GYM102538 F Farm of Monsters

There are $$$n$$$ monsters, and the $$$i$$$-th monster initially has $$$h_i$$$ health points.

Let's call a monster alive if his HP is strictly greater than zero.

You have an attack power of $$$a$$$, and your opponent has an attack power of $$$b$$$.

As long as one monster is still alive, you and your opponent take turns fighting monsters (beginning with you).

You are very smart, so on your turn, you can attack any monster that is alive or do nothing. If you choose to attack some monster $$$i$$$, the monster's health, $$$h_i$$$, will decrease by exactly $$$a$$$.

After your attack, if the monster is dead (not alive), you gain one victory point.

Your opponent, on the other hand, is not so smart. During his turn, he finds the monster with the smallest index that is alive and attacks it (i.e. he finds the smallest $$$i$$$ such that $$$h_i > 0$$$ and decreases $$$h_i$$$ exactly by $$$b$$$).

What is the greatest number of victory points that you can obtain?

The first line contains three integers $$$n,a,b$$$ ($$$1 \leq n \leq 300\,000$$$, $$$1 \leq a, b \leq 10^9$$$): the number of monsters and the attack powers of you and your opponent, respectively.

The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \leq h_i \leq 10^9$$$): the health points of the monsters.

Print one integer: the largest number of victory points that you can obtain.

3 1 1
1 1 1

2

3 1 1
2 2 2

3

10 34 100
17 27 73 17 60 12 25 53 31 46

5

In the first example, on your first turn, you can kill the third monster, and on your second turn, you can kill the second monster.

In the second example, you can wait until the leftmost monster will have $$$h_i = 1$$$, and then kill it yourself.