교수님의 기말고사

면접 대비

시간 제한1초메모리 제한1024 MB

요약

S분 동안 사용 가능한 강의실에 겹치지 않는 시험 N개가 잡혀 있을 때, 길이 M인 시험을 겹치지 않게 시작할 수 있는 가장 이른 시각을 구하고 불가능하면 -1을 출력한다.

문제

안형찬 교수님은 알고리즘 분석 기말고사를 준비하려고 한다.

알고리즘 기말고사는 총 M분 동안 쉬는 시간 없이 볼 예정이며, 인원이 너무 많아서 공학관 C040호가 아닌 다른 강의실에서는 시험을 치를 수 없게 되었다.

공학관 C040호는 0분부터 S분까지 사용 가능하다. S는 항상 M 이상이기 때문에 안 교수님은 별문제 없이 시험을 치를 것으로 생각하였다. 그러나 공학관 C040호에는 다른 시험도 예정되어 있어서 겹치지 않는 시간을 잡아야 한다.

각 시험은 xi분에 시작해서 yi분 동안 진행하며 서로 겹치지 않는다. 한 시험이 끝난 직후 다음 시험이 있는 경우도 겹치지 않는 것으로 판단한다. 즉, xi + yi ≤ xj일 때 i 시험과 j 시험은 서로 겹치지 않는다.

안형찬 교수님이 시험을 언제 치를 수 있는지 구해보자.

다음과 같이 입력이 주어진다.

N M S
x1 y1
. . .
xN y**N

교수님이 시험을 시작할 수 있는 시각을 출력하여라. 시작 가능한 시각이 여러 개 있으면 그중 가장 앞선 시각을 출력한다. 시험을 치를 수 없다면 -1을 출력하여라.