说明

时间限制：1 Sec 内存限制：256 MB 输入文件：cooperate.in 输出文件：cooperate.out

小明和小红两人组队参加了一场编程比赛。 为了参加比赛，两人拼命钻研，最终掌握了两项能力：

1. 只需瞥一眼题目，就能准确知道各自解出这道题所需的秒数；
2. 能够在 $1000$ 秒以内解出所有编程题目。 比赛即将开始。这次两人参加的比赛共有 $N$ 道题。比赛开始的瞬间，小明和小红一眼扫过所有 $N$ 道题，便掌握了每道题 $i$ 的信息：小明解出它需要的时间为 $A_i$ 秒，小红解出它需要的时间为 $B_i$ 秒。 比赛中的解题规则如下：

• 两人可以并行解题；
• 同一个人不能并行处理多道题；
• 同一道题不能由两人同时解；
• 两人都要按照顺序解自己负责的题目，中途不间隔时间。 请将 $N$ 道题合理分配给两人，求出解完所有题目所需的最短秒数。

输入格式

第一行一个整数 $N$ 表示题目的数量。 接下来 $N$ 行，每行两个整数 $A_i,B_i$ 表示小明和小红解出第 $i$ 道题需要的秒数。

输出格式

一个整数，表示合理分配的情况下，求出解完所有题目所需的最短秒数。

样例

样例 1

3
55 60
30 70
40 25

70

样例说明：小明负责第 $2,3$ 题，需要 $30+40=70$ 秒；小红负责第 $1$ 题，需要 $60$ 秒。解完所有题目需要 $70$ 秒。

样例 2

5
60 10
80 10
100 10
120 10
140 10

50

样例说明：所有题目都交给小红，总共需要 $50$ 秒。

数据范围

对于 8% 的数据，$N \le 10$。 另外 4% 的数据，$\sum A_i,\sum B_i \le 200$。 对于 100% 的数据，$1 \le N \le 100$，$1 \le A_i,B_i \le 1000$。