题目描述

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

3
6 4
8 1
2 3

输出样例

17