Description

Hopscotch, also called “jumping the airplane,” is a worldwide children’s game and one of China’s traditional folk sports.

The rules of hopscotch are as follows:

On the ground, fix a starting point, and then draw $n$ cells to the right of the start point along a straight line. Each cell contains an integer, which is the score awarded upon reaching that cell. The player starts at the start point and, on the first jump, jumps to a cell to the right of the start point. On the second jump, the player continues jumping to the right from the current position, and so on. The rules state:

• On every jump, the player must land on a cell strictly to the right of the current position. The player may end the game at any time. The final score is the sum of the numbers in all cells that have ever been reached.

Now, Xiao R has developed a bouncing robot to play this game. However, the robot has a very serious flaw: each time it jumps to the right, the distance can only be a fixed $d$. Xiao R wants to improve his robot. If he spends $g$ gold coins to improve the robot, its flexibility increases by $g$. Note that each jump distance must be at least $1$. Specifically, when $g < d$, the robot can choose its rightward jump distance each time from $d-g, d-g+1, d-g+2, \ldots, d+g-1, d+g$; otherwise, when $g \ge d$, the robot can choose its rightward jump distance each time from $1, 2, 3, \ldots, d+g-1, d+g$.

Now Xiao R wants to obtain at least $k$ points. What is the minimum number of gold coins he must spend to modify his robot?

Input Format

The first line contains three positive integers $n, d, k$, representing the number of cells, the robot’s fixed jump distance before improvement, and the desired score (at least $k$). The numbers are separated by a single space.

The next $n$ lines each contain two integers $x_i, s_i$, representing the distance from the start point to the $i$-th cell and the score of the $i$-th cell. The two numbers are separated by a single space. It is guaranteed that $x_i$ are given in increasing order.

Output Format

Output a single integer: the minimum number of gold coins required to modify the robot. If it is impossible to obtain at least $k$ points under any circumstances, output $-1$.

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

2

7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

-1

Hint

• Sample 1 explanation

After spending $2$ gold coins on improvements, Xiao R’s robot chooses rightward jump distances $2, 3, 5, 3, 4, 3$ in order, reaching positions $2, 5, 10, 13, 17, 20$, which correspond to cells $1, 2, 3, 5, 6, 7$. The sum of the numbers in these cells is $15$, which is the score obtained by Xiao R.

• Sample 2 explanation

Since the maximum possible sum of the numbers of any subset of the $7$ cells in the sample is only $18$, it is impossible to obtain $20$ points.

• Constraints

There are $10$ groups of testdata, each accounting for an equal proportion.

For all testdata, $1 \le n \le 5\times 10^5$, $1 \le d \le 2\times 10^3$, $1 \le x_i, k \le 10^9$, $|s_i| < 10^5$.

For testdata groups $1$ and $2$, $n \le 10$.

For testdata groups $3$, $4$, and $5$, $n \le 500$.

For testdata groups $6$, $7$, and $8$, $d = 1$.

Translated by ChatGPT 5