Description

约翰农夫发现他的奶牛在进行剧烈运动时会产出更高质量的牛奶。因此，他决定让他的 $N$ 头奶牛（$1 \le N \le 25,000$）去爬一座附近的山，然后再下来！

第 $i$ 头奶牛需要 $U(i)$ 的时间爬上山，然后需要 $D(i)$ 的时间爬下山。由于奶牛是家养的，每头奶牛在爬山的每一段路程中都需要农夫的帮助，但由于经济不景气，只有两位农夫可用，即约翰农夫和他的表弟唐农夫。约翰农夫计划指导奶牛上山，而唐农夫将指导奶牛下山。由于每头奶牛都需要一个向导，并且每段旅程中只有一位农夫，因此在任何时间点，最多只有一头奶牛可以在约翰农夫的帮助下爬上山，最多只有一头奶牛可以在唐农夫的帮助下爬下山。奶牛可能会在山顶暂时聚集，如果它们爬上山后需要等待唐农夫的帮助才能下山。奶牛下山的顺序可以与上山的顺序不同。

请确定所有 $N$ 头奶牛完成整个旅程所需的最短时间。

Input Format

第一行，一个整数 $N$。

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

$(1 \le U(i),D(i) \le 50,000)$。

Output Format

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

3
6 4
8 1
2 3

17

Hint

（由 ChatGPT 4o 翻译）