A2113 | $Mountain Climbing S$

来源USACO / 2012

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

农场主约翰发现他的奶牛剧烈运动后产奶的质量更高，所以他决定让 $N$ 头 $(1 \le N \le 25,000)$ 奶牛去附近爬山再返回来。 第 $i$ 头奶牛用时 $U(i)$ 爬上山，用时 $D(i)$ 下山。作为家畜，奶牛们每段路都要有农夫的帮助，可是由于经济疲软，农场里只有两个农夫 John 和 Don。John 计划引导奶牛爬山，Don 引导奶牛下山。虽然每个奶牛都需要向导，但每段旅途只有一名农夫。所有任何时刻只有一头奶牛爬山也只能有一头奶牛下山，奶牛爬上山后，可以暂时停留在山顶上等待 Don 的帮助。奶牛上山的顺序和下山的顺序不一定要相同。 请计算出所有 $N$ 头牛完成旅程的最短时间。

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

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

输入 #1

输出 #1

C++ 编辑器

输入

输出