Problem J. Jora vs Zombies

Author:A. Verkholat   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Jora is playing a game called Jora vs Zombies.

His character is positioned at coordinate 0.

Each second, Jora’s weapon can deal D damage to the nearest zombie within a radius of R.

If multiple zombies are equidistant, the damage is dealt to a random one.

A zombie dies when its health drops to zero.

Additionally, each second, zombies move one coordinate closer to Jora (after the weapon fires during that second).

The game is considered lost if any zombie reaches Jora’s position.

Your task is to determine if Jora can win the game. If he can, calculate the number of seconds required to eliminate all the zombies.

Input format

The first line contains three integers N, D, and R:

N - number of zombies.

D - damage dealt by the weapon per second.

R - weapon's effective radius.

The following N lines describe each zombie with two integers Xi and Hi:

Xi - initial coordinate of the i-th zombie.

Hi - health of the i-th zombie.

Output format

Output a single integer - the number of seconds required to eliminate all zombies.

If it is impossible to win, output -1.

Constraints

1 ≤ N ≤ 105

1 ≤ R, D, Xi, Hi ≤ 109

Sample tests

No. Standard input Standard output
1
3 4 5
15 19
7 5
4 3
15
2
1 1 3
5 4
-1
3
2 2 5
5 5
5 3
5

0.085s 0.025s 13