Wizard and wolves
Wizard and wolves
Once, while walking, you met n wolves. Each wolf has its own power parameter - health. When meeting with wolves, the i-th wolf has hi
health units. If the wolf's health drops to 0 or lower, then he dies.
Luckily, you are a wizard who can create explosions. With these explosions you can reduce the health of wolves. In one blast, the health of wolves can be reduced in the following ways:
Selecting any live wolf, you explode next to it. In this case, the health of the selected wolf is reduced by a units, and all others by b units. a and b are given to you initially.
What is the minimum number of explosions needed to make to kill all the wolves?
Input
First line contains three integers n (1 ≤ n ≤ 105
), a and b (1 ≤ b < a ≤ 109
). Each of the next n lines contains number hi
(1 ≤ hi
≤ 109
) - the health of the i-th volf.
Output
Print the minimum number of explosions needed to kill all the wolves.
Explanation
Test 1.
Let's create an explosion next to a wolf with health 8. After the explosion, the health of the wolves will be respectively 3, 4, 1, -1.
We will produce the second explosion next to a wolf with a health equal to 4. After the second explosion, all the wolves will die.
Test 2.
- To kill all the wolves, it is necessary next to each of them produce 2 explosions, overall 4 explosions. It's impossible to kill all wolves with a smaller number of explosions.
4 5 3 8 7 4 2
2
2 10 4 20 20
4
5 2 1 900000000 900000000 1000000000 1000000000 1000000000
800000000