题目描述

每天早晨，约翰的$\red{N(1≤}$$\red{N≤}$$\red{25000)}$头奶牛都排成一列，逐一挤奶．为了提高挤奶的速率

约翰把整个挤奶过程划分成两道工序，每头牛都得连续地完成这些挤奶工序．奶牛们一个接一个地进入挤奶的牛棚，约翰负责实行第一道工序，第二道工序则让他的好友萝卜帮助完成．

并且，如果某头奶牛先于另一头奶牛开始进行第一道工序，那么她开始第二道工序的时间也一定在那一头奶牛之前．

约翰发现，如果奶牛们按某种顺序排队进行挤奶，那么可能会在排队等待上多花很多的时间．比方说，如果约翰要花很长时间才能完成某头奶牛挤奶时的第一道工序，那么萝卜可能会有一段时间没有事做．当然，如果约翰的工作完成得太快，前面前就会有很多奶牛排起长队．

请你帮助约翰计算一下，如果按照最优的排队方式，最少需要多少时间才能把所有奶牛都挤过奶．对于每头奶牛，我们都知道在她身上完成第一道工序所需的时间$\red{Ai，}$ 以及完成第二道工序的时间$\red{Bi。1≤}$$\red{Ai，}$$\red{Bi≤}$$\red{20000.}$

输入格式

第$\red{1}$行一个整数$\red{N}$．接下来$\red{N}$行，每行两个整数表示第$\red{i}$头牛的$\red{Ai，}$$\red{Bi}$值．

输出格式

输出按照最优方案排队后，最少需要多少时间才能完成对所有奶牛的挤奶．

样例

输入样例

3
2 2
7 4
3 5

输出样例

16

提示

把奶牛们按照$\red{3，}$$\red{1，}$$\red{2}$的顺序排队，这样挤奶总共花费$\red{16}$个单位时间．