双子の読書感想文

双子のアミとマミが通う学校では早くも夏休みに突入し，今年もおびただしい量の宿題が出された． しかし，遊び盛りの2人は今日も宿題には一切手をつけずに外へ遊びに行こうとしていた． このままでは夏休み最終日に泣きを見るのは明らかなので，保護者役のあなたは，心を鬼にして今日は読書感想文の宿題が終わるまで2人を家から出さないことにした．

準備の良いあなたは既に図書館から全ての課題図書を借りてある． ただし，図書館の規則により各本は1冊ずつしか借りられていない． さて，教育上の理由から2人には互いに協力することなく，それぞれ全ての本を読み，感想を書いてもらう事にした． 加えて，本の返却期限が近いため，まずはなるべく早くすべての本を読み終えるようにしてもらう事にした． そして，あなたはその条件下でなるべく早く宿題が終わるような宿題の進め方を考えることにした． ここで，本を読み終えた時間，宿題を終えた時間は，それぞれ双子の両方が作業を終えた時間で考える．

各本は1冊ずつしかないため，2人が同時刻に同じ本を読むことはできない． 加えて，大人の事情により，ある本を読み始めたらそれを中断する事はできず，ある本についての感想文を書き始めたらそれを中断することもできない． 当然ながら，読んでいない本について感想を書くこともできない． なお，アミとマミは双子であるため，各本について読むのにかかる時間，感想文を書くのにかかる時間は2人で共通している．

例えば，3冊の本があり，それぞれ本を読むのにかかる時間，感想文を書くのにかかる時間が以下の通りであるとする．

この場合は，図C-1のように宿題を進めると，時間10で全ての本を読み終え，時間15で宿題を終える事ができる． 図C-2の進め方では時間14で宿題を終えているが，本を読み終える時間が最短でないため，今回は採用できない． また，図C-3のように2人が同時に同じ本を読んだり， 図C-4のように本を読むのを中断したり，読んでいない本の感想を書く事もできない．

様々な大人の事情を考慮しつつ，遊びに行きたがっている双子のためになるべく早く宿題が終わるような進め方を考えてあげよう．

Input

入力は複数のデータセットから構成される．各データセットの形式は次の通りである．

N
r1 w1
r2 w2
...
rN wN

Nは課題図書の数を表す整数であり，1以上1,000以下と仮定して良い．

続くN行は課題図書についての情報を表す． 各行はスペースで区切られた2つの整数を含み，r_i (1 ≤ r_i ≤ 1,000) は i 番目の本を読むのにかかる時間，w_i (1 ≤ w_i ≤ 1,000) は i 番目の本の感想文を書くのにかかる時間を表す．

N=0 は入力の終わりを示す． これはデータセットには含めない．

Output

各データセットについて，2人が全ての本を読み終えるまでの時間を最小にしたときの，全ての感想文を書き終えるまでの最小の時間を1行に出力しなさい．

Sample Input

4
1 1
3 1
4 1
2 1
3
5 3
1 2
1 2
1
1000 1000
10
5 62
10 68
15 72
20 73
25 75
30 77
35 79
40 82
45 100
815 283
6
74 78
53 55
77 77
12 13
39 42
1 1
0

Output for Sample Input

14
15
3000
2013
522