#9338. 「USACO12JAN」 Mountain Climbing S - 题目

时间限制：1000 ms 内存限制：256 MiB 输入文件：climb.in 输出文件：climb.out

题目类型：传统评测方式：文本比较

上传者： root

登录后提交提交记录统计讨论题解

本题采用文件输入输出。

输入文件为 climb.in，输出文件为climb.out。

农夫约翰发现，奶牛在剧烈运动后，会产出更高质量的牛奶。

因此，他决定送他的头奶牛爬上附近的山，然后再从山上下来。

奶牛的上山花费时间为，下山花费时间为。

作为家养牛，每头奶牛的爬山都要有农夫全程引导。

但是由于经济不景气，现在只有两个农名可用，分别是约翰和他的堂兄唐。

其中约翰负责引导奶牛向上爬，唐负责引导奶牛向下爬。

由于每头奶牛的爬山全过程都要有向导，而上山或下山都只有一个农夫提供引导，因此在任何时间点最多只能有一头奶牛向上爬（在约翰的协助下），并且在任何时间点最多只能有一头奶牛向下爬（在唐的协助下）。

如果一群奶牛爬上了山，它们可能会暂时聚集在山顶，然后等待唐的帮助才能爬下来。

奶牛向上爬的顺序可能与向下爬的顺序不同。

请确定所有头奶牛完成整个旅程的最短时间。

从文件 climb.in 中读入数据。

第一行包含整数。

接下来行，每行包含两个整数和。

输出到文件 climb.out 中。

输出所有奶牛完成整个旅程的最短时间。

样例输入

样例输出

样例解释

一种最佳安排方式是上山和下山都按照顺序，所花费时间为。

#9338. 「USACO12JAN」 Mountain Climbing S 省选/NOI−