Score : 600 points
Silver Fox is fighting with N monsters.
The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.
Silver Fox can use bombs to attack the monsters. Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A. There is no way other than bombs to decrease the monster's health.
Silver Fox wins when all the monsters' healths become 0 or below.
Find the minimum number of bombs needed to win.
Input is given from Standard Input in the following format:
N D A X_1 H_1 : X_N H_N
Print the minimum number of bombs needed to win.
3 3 2 1 2 5 4 9 2
2
First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.
Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.
Now, all the monsters' healths are 0. We cannot make all the monsters' health drop to 0 or below with just one bomb.
9 4 1 1 5 2 4 3 3 4 2 5 1 6 2 7 3 8 4 9 5
5
We should use five bombs at the coordinate 5.
3 0 1 300000000 1000000000 100000000 1000000000 200000000 1000000000
3000000000
Watch out for overflow.