Problem J. Jora vs Zombies ≡

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 X_i and H_i:

X_i - initial coordinate of the i-th zombie.

H_i - 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 ≤ 10⁵

1 ≤ R, D, X_i, H_i ≤ 10⁹

Sample tests

3 4 5
15 19
7 5
4 3

15

1 1 3
5 4

-1

2 2 5
5 5
5 3

5