TopCoder

Thumb 100
waynetuinfor
在線不是要用莫隊嗎 - 2017.02.15 - 周柏宇

User's AC Ratio

94.6% (53/56)

Submission's AC Ratio

58.3% (88/151)

Description

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

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

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

Input Format

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

Output Format

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

Sample Input

3
1 1
2 2
3 3
0

Sample Output

7

Hints

Problem Source

原TIOJ1072 / NPSC2005決賽(prob A)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536