60017 등교

문제

정올이는 수업에 지각하지 않기 위해 학교에 $X$분 이내로 도착해야 한다. 학교로 이동하려면 정류장에 정차하는 $N$개의 버스 중 하나를 선택하여 탑승해야 한다.

게으른 정올이는 최대한 늦게 버스를 타기 위해서 $N$개의 버스의 정보를 찾아보았다. 각 버스가 지금부터 몇 분 후에 정류장에서 출발하며, 정류장에서 출발한 버스가 학교에 도착하기 위해 몇 분이 걸리는지 알아낼 수 있었지만, 어떤 버스를 타고 학교에 갈지 아직 결정하지 못했다.

정올이를 위해서 학교에 지각하지 않는 시각에 도착하는 버스 중에서, 가장 늦게 출발하는 버스가 출발할 때까지 걸리는 시간을 구해주자. 학교에 지각하지 않도록 버스를 선택하는 방법이 없을 수도 있다.

입력

첫 번째 줄에 $N$과 $X$가 공백을 하나 사이에 두고 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐, 한 줄에 하나씩 정류장에서 버스가 출발할 때까지 걸리는 시간 S와, 버스가 정류장에서 학교까지 가는 데 걸리는 시간 $T$가 공백을 하나 사이에 두고 주어진다.

출력

학교에 $X$분 이내로 도착할 수 없다면, $-1$을 출력한다.

학교에 $X$분 이내로 도착할 수 있다면, 가장 늦게 출발하는 버스가 출발할 때까지 걸리는 시간을 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ N ≤ 100$
• $2 ≤ X ≤ 200$
• 각 버스에 대해, 정류장에서 버스가 출발할 때까지 걸리는 시간을 $S$, 버스가 정류장에서 학교까지 가는 데 걸리는 시간을 $T$라고 하자.
  • $1 ≤ S ≤ 100$
• $1 ≤ T ≤ 100$

서브태스크

1	10	$N = 1$
2	15	모든 버스는 $X$분 이내로 학교에 도착한다.
3	30	모든 버스에 대해 $T = 20$
4	45	추가 제약 조건 없음

3 8
2 1
6 3
4 4

4

1 30
15 20

-1