Road Repair

The national road is in bad condition. The pavement is damaged and needs immediate repair. Unfortunately, the repair crew assigned to the task is not very organized. Every day, they start repairing a continuous section of the road, which we know where it begins and ends. However, it is possible that on some subsequent day they may repair a section that has already been fully or partially repaired!

The national road has a total length of ~L~ kilometers. The crew has scheduled to work for ~N~ days, and on the ~k~-th day, they plan to repair the section of the road that extends from position ~S_k~ to position ~T_k~. The Ministry of Public Works wants the repair to be completed as soon as possible. It wants to know after how many days the length of the longest continuous section of the road that has not yet been repaired will not exceed ~X~.

Problem

Write a program in one of the IOI languages which, given the length ~L~ of the road, the repair crew's schedule (~N~, ~S_k~, ~T_k~), and the number ~X~, finds the minimum number of days the crew must work so that the length of the longest continuous section of the road that has not yet been repaired does not exceed ~X~. If this is never going to happen based on the crew's schedule, your program should print the number ~-1~.

Input Files:

The input files named roadwork.in are text files structured as follows: The first line contains three integers: ~N\;(1 \le N \le 1.000.000)~, ~L~ ~(1 \le L \le 1.000.000.000)~, and ~X\;(0 \le X \le L)~, separated in pairs by a single space. This is followed by ~N~ lines, each containing two integers ~S_k~, ~T_k~ ~(0 \le S_k < T_k \le L)~, separated by a single space.

Output Files:

The output files named roadwork.out are text files consisting of a single line containing a single integer ~D\;(-1 \le D \le N)~.

Examples of Input - Output Files:

1st

STDIN (roadwork.in)

4 30 6
1 5
11 27
2 14
18 28

STDOUT (roadwork.out)

2

2nd

STDIN (roadwork.in)

4 30 1
1 5
11 27
2 14
18 28

STDOUT (roadwork.out)

-1

Explanation of the examples:

In both examples, the length of the road and the schedule of the repair crew are the same, and only ~X~ differs. After the first day, the longest continuous section of the road that has not yet been repaired has a length of ~25~ (from position ~5~ to position ~30~). After the second day, it has a length of ~6~ (from position ~5~ to position ~11~). After the third day, it has a length of ~3~ (from position ~27~ to position ~30~), and after the fourth day, it has a length of ~2~ (from position ~28~ to position ~30~). Therefore, the correct answer for the 1st example is ~2~ (after the second day, the length of the longest continuous section of the road will not exceed ~X = 6~), while for the 2nd example, the correct answer is ~-1~ (the length of the longest continuous section of the road that has never been repaired will never become equal to ~X = 1~ or less).

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 2 sec.
Maximum available memory: 64 MB.