시간 관리하기

면접 대비

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

요약

각 작업의 소요 시간과 마감 시각이 주어질 때, 모든 작업을 마감 안에 끝낼 수 있는 가장 늦은 시작 시각을 구하거나 불가능하면 -1을 출력한다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬, 구간, 구현
정답자: 아직 제출이 없습니다

문제

농부 존은 시간을 효율적으로 관리하기로 했다. 그는 해야 할 일 $N$ 개( $1 \le N \le 1000$ )에 번호를 매겼다(예: 우유 짜기, 마구간 청소, 담장 고치기 등).

각 일 $i$ 를 끝내는 데 걸리는 시간을 $T_i$ ( $1 \le T_i \le 1000$ ), 그 일을 반드시 끝내야 하는 마감 시각을 $S_i$ ( $1 \le S_i \le 1{,}000{,}000$ )라고 하자. 존은 하루를 $t = 0$ 에 시작하며, 한 번 어떤 일을 시작하면 그 일을 끝낼 때까지 다른 일은 하지 않는다.

존은 늦잠을 좋아한다. 모든 일을 각자의 마감 시각까지 끝낼 수 있으면서, 존이 일을 시작할 수 있는 가장 늦은 시각을 출력하라.

입력

첫째 줄에 일의 개수 $N$ 이 주어진다.

둘째 줄부터 $N$ 개의 줄에 걸쳐 각 줄마다 $T_i$ 와 $S_i$ 가 공백으로 구분되어 주어진다.

출력

존이 일을 시작할 수 있는 가장 늦은 시각을 출력한다. 모든 일을 제시간에 끝낼 수 없다면 $-1$ 을 출력한다.

예제4

예제 1
입력
```
4
3 5
8 14
5 20
1 16
```
예상 출력
```
2
```
예제 2
입력
```
1
5 5
```
예상 출력
```
0
```
예제 3
입력
```
3
1 10
2 20
3 30
```
예상 출력
```
9
```
예제 4
입력
```
2
2 2
3 5
```
예상 출력
```
0
```