Description

小明肚子饿了，来到一家烘培店，点了n种食物。由于店里的器材损坏，这n种食物只能一种一种做。假设做这n种食物花费的时间为a[i]，小明吃完每种食物的时间为b[i]。小明实在太饿了，要求店家尽快让他吃上所有自己点的食物。店家可以任意调节做这n种食物的先后顺序，问小明吃完这n种食物最短的时间为多少？

Input

多组输入，每组第一行输入食物种数n（2<=n<=1e4），接下来一共输入n行，每一行分别输入该种食物烘焙的时间a[i]和小明吃完该种食物的时间b[i]（0<a[i],b[i]<100）

Output

输出吃完所有食物所用最短的时间。

Sample Input

3 
2 5  
4 3 
3 2

Sample Output

12

HINT

Source

NBU OJ