페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7021
서브태스크

등교 1초 1024MB

문제

정올이는 수업에 지각하지 않기 위해 학교에 X분 이내로 도착해야 한다.

학교로 이동하려면 정류장에 정차하는 N개의 버스 중 하나를 선택하여 탑승해야 한다.

게으른 정올이는 최대한 늦게 버스를 타기 위해서 N개의 버스의 정보를 찾아보았다.

각 버스가 지금부터 몇 분후에 정류장에서 출발하며,
정류장에서 출발한 버스가 학교에 도착하기 위해 몇 분이 걸리는지 알아낼 수 있었지만,
어떤 버스를 타고 학교에 갈지 아직 결정하지 못했다.

정올이를 위해서 학교에 지각하지 않는 시각에 도착하는 버스 중에서,
가장 늦게 출발 하는 버스가 출발할 때까지 걸리는 기간을 구해주자.

학교에 지각하지 않도록 버스를 선택하는 방법이 없을 수도 있다.


입력

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

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

[제약 조건]

주어지는 모든 수는 정수이다.

  • 1 ≤ N ≤ 100

  • 2 ≤ X ≤ 200

각 버스에 대해, 정류장에서 버스가 출발할 때까지 걸리는 시간을 S, 버스가 정류장에서 학교까지 가는 데 걸리는 시간을 T라고 하자.

  • 1 ≤ S ≤ 100

  • 1 ≤ T ≤ 100


출력

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

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


부분문제

번호 점수 조건
#110점

N = 1

#215점

모든 버스는 X분 이내로 학교에 도착한다.

#330점

모든 버스에 대해 T = 20

#445점

추가 제약 조건 없음


예제1

입력
38
31
63
44
출력
4

예제2

입력
130
1520
출력
-1

태그

출처

KOI 1차 2024 초1

역링크