Professor's Final Exam

Interview

Time limit1sMemory limit1024 MB

Summary

Given N non-overlapping exams in a room open for S minutes, find the earliest start time for a new exam of length M that fits without overlap, or -1.

Level: Medium4 of 10
Topics: Sorting, Intervals, Greedy, Implementation
Solved: No attempts yet

Problem

Professor Ahn Hyungchan is preparing the final exam for his algorithm analysis course.

The final exam will run for M minutes with no break, and because the class is so large it cannot be held anywhere except room C040 in the engineering building.

Room C040 is available from minute 0 to minute S. Since S is always at least M, the professor thought the exam could be held without trouble. However, other exams are also scheduled in room C040, so he must pick a time slot that does not overlap with any of them.

Each exam starts at minute xi and runs for yi minutes, and no two exams overlap. An exam that starts right after another exam ends also counts as non-overlapping. That is, exam i and exam j do not overlap when xi + yi ≤ xj.

Find when Professor Ahn can hold his exam.

Input

The input is given as follows.

N M S
x1 y1
. . .
xN y**N

Output

Print the time at which the professor can start the exam. If more than one start time is possible, print the earliest one. If the exam cannot be held, print -1.

Constraints

1 ≤ N ≤ 100,000.
1 ≤ M ≤ S ≤ 1,000,000,000.
0 ≤ xi < xi + yi ≤ S.
Every number in the input is an integer.

Examples2

Example 1
Input
```
2 3 5
0 1
4 1
```
Expected output
```
1
```
Example 2
Input
```
2 3 5
0 2
4 1
```
Expected output
```
-1
```