TopCoder

Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

94.5% (395/418)

Submission's AC Ratio

42.3% (581/1373)

Tags

Description

經過了一整天漫長難熬的上課時間之後,期待了一整天下課的小尹終於能夠暫時逃離課業的轟炸,回到他最喜歡的休閒活動 - 楓之谷的懷抱了!正當小尹迫不及待的連上網路準備大展身手之時,肚子卻不聽使喚的抗議的起來,於是他只好決定先去飽餐一頓回來,晚上才有力氣好好廝殺。

一陣呼朋引伴之後小尹和他的同學們來到了最近的小吃店,每個人選好了菜單上自己想要吃的餐點,正準備要把菜單遞給老闆的時候,小尹卻突然叫大家停了下來,他說:「你看哦,我們有人吃飯快有人吃飯慢,每道菜煮好送上來的時間也不一樣。如果我先吃完,還要等你們吃,又不想拋棄你們自己先回去。那麼如果老闆送菜順序不對的話,我就可能要等很久才能回去玩。最好是我們自己先想好理想的上菜順序,告訴老闆請他照著順序煮菜,才能讓我們大家一起早點回去玩,這樣好不好?」

超有行動力的小尹馬上就開始收集這家小吃店的資訊。他發現這家店很不幸的只有一組廚具,而每份餐點都必須分開來煮,一道煮完才能煮另外一道。而且菜單上每份餐點也都有不同的烹煮時間:例如蛋炒飯可能很快就好了,水餃因為要現包就要等久一點。同時小尹也調查了大家吃飯的速度,估算出每個人吃他所點的餐所需要的時間 (我們假設每個人只有點一份餐)。每份餐點煮好了之後會馬上上桌且立即可食用,而老闆也可以同時緊接著煮下一道菜。小尹身為一個資訊系的學生,有了這些資料之後二話不說就拿出了電腦,想要寫個程式來解決這個問題,可是一時之間卻好像想不到理想的解法。你能幫小尹想個辦法,讓他盡可能早點回到楓之谷的世界嗎?

Input Format

輸入檔包含多組測試資料,每一組測試資料的第一行有一個整數 $N (1 \le N \le 10000)$ ,代表跟小尹去吃飯的人數,接下來的 $N$ 行每行有兩個以空白字元分隔的整數 $C_i, E_i (\forall 1 \le i \le N, 1 \le C_i, E_i \le 1000)$ ,其中 $C_i$ 代表烹煮第 $i$ 個人點的餐點所需要的時間,$E_i$ 代表第 $i$ 個人把他點的餐點吃完所需要的時間。讀到 $N = 0$ 的時候代表測試檔案的結尾,不需要對於這個數字作任何輸出。

Output Format

對於每一組測試檔,輸出一個正整數在一行內,代表「從老闆開始煮第一道餐點開始,到最後一個人吃完為止,中間一共花了多少時間」,這個數字應該越小越好。

Sample Input 1

3
1 1
2 2
3 3
0

Sample Output 1

7

Hints

Problem Source

原TIOJ1072 / NPSC2005決賽(prob A)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1900 65536 262144 1