Exhibition 2

Time limit1sMemory limit1024 MB

Summary

Choose M of N paintings spaced at least D apart to maximize the minimum value among the chosen paintings, or report that no such choice exists.

Level: Medium7 of 10
Topics: Binary search, Dynamic programming, Sorting, Greedy
Solved: No attempts yet

Problem

In the JOI Museum, N paintings hang along a corridor that runs straight east to west, numbered from 1 to N. Painting i (1 ≦ i ≦ N) hangs Xi meters from the west end of the corridor, and its value is Vi.

Starting tomorrow, the museum will hold the "Egoi Exhibition", and a very large number of visitors are expected. The Egoi Exhibition will display M paintings.

Since two paintings displayed close together are hard to see, we decided to remove N-M paintings and leave only M paintings in the corridor so that the following condition holds.

Any two paintings must be at least D meters apart.

The minimum value among the M displayed paintings is called the splendor of the Egoi Exhibition. By choosing the M paintings to leave in the corridor well, you want to make the splendor of the Egoi Exhibition as large as possible.

Given the information on the N paintings and the number of paintings to leave in the corridor, write a program that determines whether a way to leave the paintings satisfying the condition exists, and if it does, finds the maximum splendor of the Egoi Exhibition.

Input

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

N M D
X1 V1
X2 V2
:
XN VN

Output

If no way to leave the paintings satisfying the condition exists, output -1 on a single line to standard output.

If a way to leave the paintings satisfying the condition exists, output the maximum splendor of the Egoi Exhibition on a single line to standard output.

Constraints

1 ≦ N ≦ 100 000.
1 ≦ M ≦ N.
1 ≦ D ≦ 1 000 000 000.
1 ≦ Xi ≦ 1 000 000 000 (1 ≦ i ≦ N).
Xi ≠ Xj (1 ≦ i < j ≦ N).
1 ≦ Vi ≦ 1 000 000 000 (1 ≦ i ≦ N).
All input values are integers.

Examples5

Example 1
Input
```
3 1 34
10 250
30 200
50 500
```
Expected output
```
500
```
Example 2
Input
```
4 4 10
21 160
32 270
11 115
44 205
```
Expected output
```
115
```
Example 3
Input
```
4 4 14
21 160
32 270
11 115
44 205
```
Expected output
```
-1
```
Example 4
Input
```
6 3 4
4 2
5 2
2 1
9 2
1 1
7 2
```
Expected output
```
1
```

Example 5

Input

Expected output