Arrested Development

면접 대비

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

요약

각 업무를 두 인턴이 처리하는 데 걸리는 시간이 주어질 때, 두 사람의 총 작업 시간 중 큰 값이 최소가 되도록 업무를 나누는 문제입니다.

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

문제

You are now in charge of two programming interns, and you must develop a large system. There are a number of tasks that need to be completed by the end of the summer. You know how long each intern will take to complete each task, in minutes.

Compute the minimum number of minutes it will take to complete all tasks for development of the system, assuming that the two interns are the only developers, that they work independently and concurrently, that they do not share tasks, and that the amount of time it takes an intern to complete all their tasks is the sum of the number of minutes it takes to do each task one after the other.

입력

The first line of input contains a single integer $n$ ( $1 \le n \le 50$ ), which is the number of tasks.

Each of the next $n$ lines contains two integers $a$ and $b$ ( $1 \le a,b \le 10^5$ ). Each line represents a single task, where $a$ is the number of minutes it will take the first intern to complete the task, and $b$ is the number of minutes it will take the second intern to complete the task.

출력

Output a single integer, which is the minimum number of minutes needed to complete the development project.

예제2

예제 1
입력
```
4
100 1
1 90
1 20
1 20
```
예상 출력
```
3
```
예제 2
입력
```
2
314 1
592 6
```
예상 출력
```
7
```