Exhibition 2

The JOI Art Museum has a corridor that extends straight in the east-west direction, on which N paintings are hung. The paintings are numbered from 1 to N. Painting i (1 ≦ i ≦ N) is hung at a position X_i meters from the west end of the corridor, and its value is V_i.

The museum is scheduled to hold the "Egoi Exhibition" starting tomorrow, and a very large number of visitors is expected. The "Egoi Exhibition" is planned to display M paintings.

Since it is difficult to view two paintings when they are hung close to each other, the museum decided to remove N-M paintings so that only M paintings remain in the corridor, satisfying the following condition.

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

The brilliance of the "Egoi Exhibition" is defined as the minimum value among the M displayed paintings. You want to choose the M paintings to remain in the corridor wisely so as to maximize the brilliance of the "Egoi Exhibition".

Given the information of the N paintings and the number of paintings to remain in the corridor, write a program that determines whether there exists a way to keep the paintings satisfying the condition, and if it exists, computes the maximum possible brilliance of the "Egoi Exhibition".

Constraints

• 1 ≦ N ≦ 100000.
• 1 ≦ M ≦ N.
• 1 ≦ D ≦ 1000000000.
• 1 ≦ X_i ≦ 1000000000 (1 ≦ i ≦ N).
• X_i ≠ X_j (1 ≦ i < j ≦ N).
• 1 ≦ V_i ≦ 1000000000 (1 ≦ i ≦ N).
• All input values are integers.

Input

The input is given from standard input in the following format.
N M D
X₁ V₁
X₂ V₂
:
X_N V_N

Output

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

If there is a way to keep the paintings satisfying the condition, output the maximum possible brilliance of the "Egoi Exhibition" in one line to standard output.

Sample Input and Output

Sample Input 1

3 1 34
10 250
30 200
50 500

Sample Output 1

500

If only painting 3 is kept, the brilliance of the "Egoi Exhibition" is 500. Since the brilliance cannot be made larger than 500, output 500.

Sample Input 2

4 4 10
21 160
32 270
11 115
44 205

Sample Output 2

115

All paintings can be kept, and the brilliance of the "Egoi Exhibition" is 115.

Sample Input 3

4 4 14
21 160
32 270
11 115
44 205

Sample Output 3

-1

It is impossible to keep the paintings such that any two paintings are at least 14 meters apart. Therefore, output －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

---