题目描述

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.

4
100 1
1 90
1 20
1 20

3

2
314 1
592 6

7