配对

题目描述

农夫约翰发现，一头奶牛在产奶时，如果附近有另一头奶牛作为精神支柱，那么它的产奶量就会大大增加。

因此，他想把他的 $M$ 头奶牛分成 $M/2$ 对。

然后，每对奶牛将被领到牛棚中一个单独的位置上挤奶。

$M/2$ 个位置上的挤奶将同时进行。

让事情变得复杂一点的是，每头奶牛都有不同的产奶量。

如果产奶量为 $A$ 和 $B$ 的两头奶牛配对，则总共需要 $A+B$ 个单位的时间来产奶。

请帮助约翰确定完成整个挤奶过程所需的最短时间，假设他以最佳方式将奶牛配对。

输入格式

第一行包含整数 $N$。

接下来 $N$ 行，每行包含两个整数 $x,y$，表示约翰有 $x$ 头产奶量为 $y$ 的奶牛。

上述 $N$ 行，所有 $x$ 的和即为 $M$，也就是奶牛的总数。

输出格式

输出以最佳方式将奶牛配对的情况下，完成整个挤奶过程所需的最短时间。

3
1 8
2 5
1 2

10

提示

#### 数据范围与提示 $1≤N≤10^5, 2≤M≤10^9$, $M$ 是偶数, $1≤y≤10^9$ #### 样例解释 最佳配对方式为 8,2 配对与 5,5 配对。 这样，每对奶牛的挤奶总时间都为 10，因为挤奶是同时进行的，所以总时间为 10。

来源

童程童美