题目描述

农场主约翰发现他的奶牛剧烈运动后产奶的质量更高，所以他决定让${N}$头${(1 <= N <= 25,000)}$奶牛去附近爬山再返回来。

第${i}$头奶牛用时${U(i)}$爬上山，用时${D(i)}$下山。作为家畜，奶牛们每段路都要有农夫的帮助，可是由于经济疲软，农场里只有两个农夫${John}$和${Don}$。${John}$计划引导奶 牛爬山，${Don}$引导奶牛下山。虽然每个奶牛都需要向导，但每段旅途只有一名农夫。所有任何时刻只有一头奶牛爬山也只能有一头奶牛下山，奶牛爬上山后，可以暂时停留在山顶上等待${Don}$的帮助。 奶牛上山的顺序和下山的顺序不一定要相同。

请计算出所有${N }$头牛完成旅程的最短时间。

输入格式

第一行，一个整数${N}$

第${2 }$到第${N+1 }$行，每行两个用空格隔开的整数${U(i)}$和${D(i)}$。

${(1 <= U(i), D(i) <= 50,000).}$

输出格式

一行一个整数，表示所有${N }$头牛完成旅程的最短时间。

样例

输入样例

3
6 4
8 1
2 3

输出样例

17