P3669 [USACO17OPEN] Paired Up S

题目描述

Farmer John 发现，当他的奶牛附近有另一头奶牛提供精神支持时，每头奶牛挤奶会更容易。因此，他希望将他的 $M$ 头奶牛（$M \leq 1,000,000,000$，$M$ 为偶数）分成 $M/2$ 对。每对奶牛将被引导到谷仓中一个单独的隔间进行挤奶。这些 $M/2$ 个隔间中的挤奶过程将同时进行。

为了增加一些复杂性，Farmer John 的每头奶牛都有不同的产奶量。如果产奶量分别为 $A$ 和 $B$ 的两头奶牛被配对，那么挤完它们总共需要 $A+B$ 单位时间。

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

输入格式

输入的第一行包含 $N$（$1 \leq N \leq 100,000$）。

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

输出格式

输出 Farmer John 的奶牛挤奶所需的最少时间，假设它们以最佳方式配对。

输入输出样例 1

3
1 8
2 5
1 2

10

说明/提示

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