3. Advertising
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a certain country, it was decided to start combating the overwhelming amount of advertising on television channels.To this end, a law was passed stipulating that the total amount of advertising time in any given hour should not exceed $$$T$$$ seconds.Write a program that will check for compliance with this law.

Input

The first line of the input contains an integer $$$N$$$ — the number of advertising inserts during the checked period ($$$1 \le N \le 10^5$$$).

The second line contains an integer $$$T$$$ ($$$0 \le T \lt 3600$$$).

Each of the next $$$N$$$ lines contains two integers $$$t_1$$$ and $$$t_2$$$ separated by a space — the start and end times of the next advertising insert ($$$0 \le t_1 \lt t_2 \le 10^9$$$). The times are given in seconds from the start of the check. The times are ordered in ascending order (i.e., in each subsequent line, $$$t_1$$$ is greater than $$$t_2$$$ in the previous line).

Output

If there is such an hour (that is, an interval of time lasting 3600 seconds) in which there was more than $$$T$$$ seconds of advertising, then output a single integer — the start time of such an interval. If there are multiple correct answers, output the smallest non-negative one. If the sought interval does not exist, output -1.

Scoring

Each test is evaluated independently. The tests are divided into groups corresponding to the following subtasks:

SubtaskAdditional ConditionsPoints
$$$1$$$$$$N \le 100$$$, $$$t_2 \le 10^4$$$30
$$$2$$$$$$N \le 10^5$$$, $$$t_2 \le 10^6$$$30
$$$3$$$-40
Examples
Input
3
1000
0 100
5000 5300
6000 7000
Output
3101
Input
1
3599
0 3599
Output
-1
Note

Reminder for those solving in Python: to input two integers separated by a space, you can do it like this: 

t1, t2 = map(int, input().split())