Paired Up

题目描述

Farmer John 发现，当奶牛附近有另一头奶牛提供精神支持时，它们更容易被挤奶。因此，他想把他的 $M$ 头奶牛（$M \leq 1,000,000,000$，且 $M$ 为偶数）划分成 $M/2$ 对。每一对奶牛随后会被带到牛棚中一个单独的畜栏里挤奶。这 $M/2$ 个畜栏的挤奶将同时进行。

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

请帮助 Farmer John 确定：在以最优方式配对的前提下，整个挤奶过程完成所需的最短可能时间。

输入格式

输入格式（文件 pairup.in）： 第一行输入包含 $N$（$1 \leq N \leq 100,000$）。接下来的 $N$ 行每行包含两个整数 $x$ 和 $y$，表示 FJ 有 $x$ 头产奶量为 $y$ 的奶牛（$1 \leq y \leq 1,000,000,000$）。所有 $x$ 的和为 $M$，即奶牛总数。

输出格式

输出格式（文件 pairup.out）： 输出在最优配对情况下，FJ 的奶牛全部挤完奶所需的最少时间。

3
1 8
2 5
1 2

10

提示

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

题目鸣谢：Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver