Problem Description

In the JOI Art Museum, there are $ N $ paintings hung along a straight corridor running east-west, numbered from $ 1 $ to $ N $. Painting $ i $ ($1 \leq i \leq N$) is hung $ X_i $ meters from the west end of the corridor, and its value is $ V_i $.

Tomorrow, an exhibition called "Egoi-Ten" is scheduled to open, and it is expected to attract a large number of visitors. In this exhibition, $ M $ paintings are planned to be displayed.

Since two paintings close to each other are difficult to view, it was decided to remove $ N-M $ paintings and leave only $ M $ paintings in the corridor, satisfying the following condition:

• For any two paintings, their positions must be at least $ D $ meters apart.

The minimum value of the $ M $ displayed paintings is defined as the brilliance of the "Egoi-Ten". You want to maximize the brilliance of the "Egoi-Ten" by choosing the $ M $ paintings to leave in the corridor.

Given the information of the $ N $ paintings and the number of paintings to leave in the corridor, determine if there exists a way to leave the paintings satisfying the condition. If it exists, create a program to find the maximum brilliance of the "Egoi-Ten".

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ D $ $ X_1 $ $ V_1 $ $ X_2 $ $ V_2 $ $\vdots$ $ X_N $ $ V_N $

Output Format

If there is no way to leave the paintings satisfying the condition, output -1 in one line to the standard output.

If there is a way to leave the paintings satisfying the condition, output the maximum brilliance of the "Egoi-Ten" in one line to the standard output.

Sample Input and Output

Sample Input #1

3 1 34
10 250
30 200
50 500

Sample Output #1

500

Sample Input #2

4 4 10
21 160
32 270
11 115
44 205

Sample Output #2

115

Sample Input #3

4 4 14
21 160
32 270
11 115
44 205

Sample Output #3

-1

Sample Input #4

6 3 4
4 2
5 2
2 1
9 2
1 1
7 2

Sample Output #4

1

Sample Input #5

15 6 129
185 2821
683 3312
101 3406
485 2120
671 1992
869 2555
872 3123
237 2970
351 2374
996 2090
729 2686
375 2219
820 3085
511 3217
924 4229

Sample Output #5

2219

Notes/Hints

Constraints

• $1 \leq N \leq 100,000$.
• $1 \leq M \leq N$.
• $1 \leq D \leq 1,000,000,000$.
• $1 \leq X_i \leq 1,000,000,000$ ($1 \leq i \leq N$).
• $X_i \neq X_j$ ($1 \leq i < j \leq N$).
• $1 \leq V_i \leq 1,000,000,000$ ($1 \leq i \leq N$).
• All input values are integers.

Subtasks

1. ($ 3 $ points) $ M = 1 $.
2. ($ 12 $ points) $ M = N $.
3. ($ 19 $ points) $N \leq 15$.
4. ($ 17 $ points) $N \leq 1,000$, $V_i \leq 2$ ($1 \leq i \leq N$).
5. ($ 22 $ points) $N \leq 1,000$.
6. ($ 27 $ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the scores of the subtasks it correctly solves.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked under the "My Score Status" tab in the "Submission Results".

Sample Explanation 1

If only Painting $ 3 $ is left, the brilliance of the "Egoi-Ten" is $ 500 $. Since it is not possible to make the brilliance greater than $ 500 $, output $ 500 $. This input example satisfies the constraints of Subtasks $ 1, 3, 5, 6 $.

Sample Explanation 2

All paintings can be left, and the brilliance of the "Egoi-Ten" is $ 115 $. This input example satisfies the constraints of Subtasks $ 2, 3, 5, 6 $.

Sample Explanation 3

It is not possible to leave any two paintings at least $ 14 $ meters apart. Therefore, output -1. This input example satisfies the constraints of Subtasks $ 2, 3, 5, 6 $.

Sample Explanation 4

This input example satisfies the constraints of Subtasks $ 3, 4, 5, 6 $.

Sample Explanation 5

This input example satisfies the constraints of Subtasks $ 3, 5, 6 $.

见题面 Input 部分

见题面 Output 部分