Going to School

Interview

Time limit1sMemory limit1024 MB

Summary

Given N buses with departure time S and travel time T, find the latest departure among buses where S + T is at most X, or print -1 if none qualify.

Level: Easy1 of 10
Topics: Implementation, Array
Solved: No attempts yet

Problem

Jeongol must reach school within $X$ minutes to avoid being late for class. To get there, he must choose one of the $N$ buses that stop at the bus stop and board it.

Jeongol wants to board as late as possible. He looked up information on all $N$ buses. For each bus, he found out how many minutes from now it leaves the bus stop and how many minutes it takes to get from the bus stop to school. He has not yet decided which bus to take.

Among the buses that get him to school on time, find the time until the latest-departing bus leaves. It is possible that no bus gets him to school on time.

Input

The first line contains $N$ and $X$ , separated by a single space.

Each of the next $N$ lines contains $S$ and $T$ , separated by a single space. $S$ is the number of minutes from now until the bus leaves the bus stop, and $T$ is the number of minutes the bus takes to get from the bus stop to school.

Output

If Jeongol cannot reach school within $X$ minutes, print $-1$ .

Otherwise, print the number of minutes until the latest-departing bus that gets him to school on time leaves the bus stop.

Constraints

All given numbers are integers.

$1 \le N \le 100$
$2 \le X \le 200$
For each bus, $S$ $S$ is the number of minutes until it leaves the bus stop, and $T$ $T$ is the number of minutes it takes to get from the bus stop to school.
- $1 \le S \le 100$
- $1 \le T \le 100$

Examples2

Example 1
Input
```
3 8
2 1
6 3
4 4
```
Expected output
```
4
```
Example 2
Input
```
1 30
15 20
```
Expected output
```
-1
```