Background

NOIP2017 Junior Group T4

Problem Description

Hopscotch, also known as "jumping planes," is a global children's game and one of the traditional Chinese folk sports.

The rules of hopscotch are as follows:

Determine a starting point on the ground, and then draw $n$ squares to the right of the starting point, all in a straight line. Each square contains an integer representing the score obtained by landing in that square. The player starts from the starting point and jumps to a square to the right of the starting point. The player then continues to jump to the right from their current position, and so on. The rules stipulate:

The player must always jump to a square to the right of their current position. The player can end the game at any time, and the score is the sum of the integers in the squares they have landed in.

Now, Xiao R has developed a hopping robot to participate in this game. However, the robot has a severe flaw: it can only jump a fixed distance $d$ to the right. Xiao R wants to improve his robot. If he spends $g$ gold coins to improve the robot, the robot's flexibility will increase by $g$, but it is important to note that the jumping distance must be at least $1$. Specifically, when $g < d$, the robot can choose to jump distances of $d-g, d-g+1, d-g+2, \ldots, d+g-1, d+g$; otherwise, when $g \geq d$, the robot can choose to jump distances of $1, 2, 3, \ldots, d+g-1, d+g$.

Xiao R hopes to score at least $k$ points. How many gold coins does he need to spend to improve his robot?

Input Format

The first line contains three positive integers $n, d, k$, representing the number of squares, the fixed jumping distance of the robot before improvement, and the desired minimum score, respectively. The numbers are separated by a space.

The next $n$ lines each contain two integers $x_i, s_i$, representing the distance from the starting point to the $i$-th square and the score of the $i$-th square, respectively. The numbers are separated by a space. The $x_i$ values are guaranteed to be input in increasing order.

Output Format

A single line containing an integer, representing the minimum number of gold coins needed to improve the robot. If it is impossible to achieve at least $k$ points, output $-1$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #2

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

Sample Output #2

-1

Notes

Sample 1 Explanation

After spending 2 gold coins to improve the robot, Xiao R's robot chooses the following jumping distances: $2, 3, 5, 3, 4, 3$, landing at positions $2, 5, 10, 13, 17, 20$, corresponding to squares $1, 2, 3, 5, 6, 7$. The sum of the scores in these squares, $15$, is the score Xiao R obtains.

Sample 2 Explanation

Since the maximum possible sum of scores from the 7 squares in the sample is only $18$, it is impossible to achieve $20$ points.

Data Constraints

This problem consists of 10 test cases, each equally weighted.

For all data, it is guaranteed that $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 the first two test cases, it is guaranteed that $n \le 10$.

For the third, fourth, and fifth test cases, it is guaranteed that $n \le 500$.

For the sixth, seventh, and eighth test cases, it is guaranteed that $d = 1$.

见题面 Input 部分

见题面 Output 部分