b042: A. 誰先晚餐

本題出處 http://zerojudge.tw/ShowProblem?problemid=b042

內容 ：

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

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

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

輸入說明 ：

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

輸出說明 ：

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

範例輸入 ：

3

1 1

2 2

3 3

0

範例輸出 ：

7

提示 ：

出處 ：

2005 NPSC 高中組決賽

解題策略

排序吃與煮比較久(吃相同時，比較煮)的先做，吃的時間*10000加上煮的時間來排序，就後再除10000與求餘數，回到原來的吃與煮時間。