|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||8||7||6||85.714%|
There are n monsters, and the i-th monster initially has hi 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, hi, 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 hi > 0 and decreases hi 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 ≤ n ≤ 300 000, 1 ≤ a, b ≤ 109): the number of monsters and the attack powers of you and your opponent, respectively.
The second line contains n integers h1, h2, . . . , hn (1 ≤ hi ≤ 109): 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
3 1 1 2 2 2
10 34 100 17 27 73 17 60 12 25 53 31 46
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 hi = 1, and then kill it yourself.