Wizard and wolves#8598
Once, while walking, you met wolves. Each wolf has its own power parameter - health. When meeting with wolves, the -th wolf has h_i health units. If the wolf's health drops to 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 units, and all others by units. and are given to you initially.
What is the minimum number of explosions needed to kill all the wolves?
First line contains three integers (1 \le n \le 10^5), and (1 \le b < a \le 10^9). Each of the next lines contains number h_i (1 \le h_i \le 10^9) - the health of the -th wolf.
Print the minimum number of explosions needed to kill all the wolves.
Example 1
Example 2
Example 3
Test 1.
- Let's create an explosion next to a wolf with health . After the explosion, the health of the wolves will be respectively , , , .
- We will produce the second explosion next to a wolf with a health equal to . 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 explosions, overall explosions. It's impossible to kill all wolves with a smaller number of explosions.