背景

\(SBW\)最近在玩一款名叫"Girl's Debug Diary"的游戏
游戏内容是帮助自己学习OI的妹妹和女友Debug
Debug成功，对方的好感度就会上升
理所当然的，游戏目标是让女友好感度尽可能大
然而还有个妹妹存在……

描述

日记共有N天
每天妹妹和女友会各拿出一份代码让\(SBW\)Debug
根据问题的难易，Debug成功可以得到一定的好感度
然而\(SBW\)水平不够，一天只能Debug一份代码
妹妹要求N天结束后自己的好感度要大于等于女友的
否则就制作“美味”的肉饼给\(SBW\)吃
好消息是，由于妹妹是妹妹
好感度好像提得会相对快一点
求N天后女友的最大好感度

输入

第一行一个数N
接下来N行，每行两个数Ai,Bi
Ai表示Debug女友代码，女友的好感度增量
Bi表示Debug妹妹代码，妹妹的好感度增量

输出

一行一个数Love，表示女友的最大好感度

样例

输入

5
1 5
4 4
3 2
3 3
1 6

输出

10

解释

第一天和最后一天Debug妹妹代码
另外三天Debug女友的即可

范围

5% N<=15 Ai<=30 Bi<=10
25% N<=20 Ai<=50 Bi<=70
50% N<=100 Ai<=200 Bi<=300
70% N<=500 Ai<=200 Bi<=1000
85% N<=1000 Ai<=300 Bi<=3000
100% 5<=N<=1500 0<=Ai<=400 0<=Bi<=40000

限制

1s
64M