题目描述

下课铃终于响了，你和一群朋友（共 $N$ 人）一起冲到食堂。因为你们到的非常早，现在食堂窗口前面还没有人。食堂共有两个窗口。你们每个人打饭会耗时 $a_i$ ，打完立刻去座位上吃饭会耗时 $b_i$ ，由于你们吃完饭要一起打球，所以你们希望最后一个人吃完饭的时间尽可能早。现在，你要安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

输入格式

第一行一个整数 $N$ ，表示共有 $N$ 人。

接下来 $N$ 行，每行两个整数 $a_i,b_i$ ，表示每个人打饭和吃饭的用时。

输出格式

一个整数，表示所有人吃完饭的最早时间。

数据范围

对于 20% 的数据，$N\leq 5$ 。

对于 40% 的数据，$N\leq 20$ 。

对于另外 20% 的数据，每个人吃饭时间都一样。

对于 100% 的数据，$1\leq N,a_i,b_i\leq 500$ 。

输入输出样例

输入样例1

5
2 2
7 7
1 3
6 4
8 5

输出样例1

17

输入/输出样例2

见下发文件，满足每个人吃饭时间相同。

输入/输出样例3

见下发文件。