该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

USACO 2017 US Open Contest, Silver

题目描述

农夫约翰发现，他的奶牛在挤奶时如果旁边有另一头奶牛陪伴，会更容易挤奶。因此，他想要将他的 $M$ 头奶牛（$M \leq 1,000,000,000$，$M$ 为偶数）分成 $M/2$ 对。每对奶牛将被带到谷仓中一个独立的隔间进行挤奶。这 $M/2$ 个隔间的挤奶将同时进行。

让事情变得稍微复杂的是，农夫约翰的每头奶牛都有不同的产奶量。如果将产奶量为 $A$ 和 $B$ 的两头奶牛配对，那么挤完这两头奶牛总共需要 $A+B$ 单位时间。

请帮助农夫约翰确定，假设他以最优方式配对奶牛，整个挤奶过程完成所需的最短可能时间是多少。

输入格式

第一行包含一个整数 $N$（$1 \leq N \leq 100,000$）。

接下来 $N$ 行，每行包含两个整数 $x$ 和 $y$，表示农夫约翰有 $x$ 头产奶量为 $y$ 的奶牛（$1 \leq y \leq 1,000,000,000$）。所有 $x$ 的和为 $M$，即奶牛的总数。

输出格式

输出一个整数，表示在最优配对方式下，完成挤奶所需的最短时间。

输入输出样例

输入 #1

3
1 8
2 5
1 2

输出 #1

10

样例解释

这里，如果将产奶量为 8 和 2 的奶牛配对，将产奶量为 5 和 5 的两头奶牛配对，那么两个隔间都需要 10 单位时间挤奶。由于挤奶是同时进行的，整个挤奶过程将在 10 单位时间后完成。任何其他配对方式都会导致某个隔间需要超过 10 单位时间，因此不是最优的。

数据范围

• $1 \leq N \leq 100,000$
• $1 \leq y \leq 1,000,000,000$
• $M = \sum x \leq 1,000,000,000$，且 $M$ 为偶数