Training, Round 4

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

요약

각 문제를 순서대로 풀면서 풀고 나면 두 능력치 중 하나를 1 올릴 수 있을 때, 모든 문제의 난이도를 만족시키는 초기 두 능력치 합의 최솟값을 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 이분 탐색, 구현
정답자: 아직 제출이 없습니다

문제

T1 Ashley is training for another programming contest on Brandon's Online Judge. Brandon's Online Judge still has the same feature which allows Ashley's coach, Tom, to load in a list of problems for Ashley to work on.

Tom has curated some problems for Ashley to work on. Each problem is parameterized by "implementation difficulty" and "thinking difficulty", both of which are positive integers. Ashley must solve them in order.

Ashley starts out with a given implementation skill and thinking skill level. Ashley can solve a problem if and only if her implementation skill level is greater than or equal to the implementation difficulty of the problem, and her thinking skill level is greater than or equal to the thinking difficulty of the problem. After solving a problem, exactly one of her implementation skill level and thinking skill level increases by $1$ , and Ashley can pick which increases.

Compute the minimum possible sum of implementation and thinking skill levels that Ashley can start out with such that she can solve all the problems on Tom's list in order.

입력

The first line contains a single integer $n$ ( $1 \le n \le 50$ ).

The next $n$ lines each contain two integers, $i$ and $t$ $(1 \le i, t \le 10^9)$ , representing the implementation and thinking difficulties of one of the problems on Tom's list.

The problems are presented in the order that Ashley must solve them.

출력

Output a single integer, the minimum possible sum of implementation and thinking skill levels that Ashley can start out with such that she can solve all the problems on Tom's list in order.

예제3

예제 1
입력
```
3
4 4
5 1
1 5
```
예상 출력
```
8
```
예제 2
입력
```
3
4 4
1 6
6 1
```
예상 출력
```
10
```
예제 3
입력
```
2
33 33
34 34
```
예상 출력
```
67
```