#1024. 「USACO 2012.1 Silver」Mountain Climbing

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
climb.in ≫ climb.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

约翰农夫发现他的奶牛在进行剧烈运动时会产出更高质量的牛奶。因此,他决定让他的 头奶牛()去爬一座附近的山,然后再下来!

头奶牛需要 的时间爬上山,然后需要 的时间爬下山。由于奶牛是家养的,每头奶牛在爬山的每一段路程中都需要农夫的帮助,但由于经济不景气,只有两位农夫可用,即约翰农夫和他的表弟唐农夫。约翰农夫计划指导奶牛上山,而唐农夫将指导奶牛下山。由于每头奶牛都需要一个向导,并且每段旅程中只有一位农夫,因此在任何时间点,最多只有一头奶牛可以在约翰农夫的帮助下爬上山,最多只有一头奶牛可以在唐农夫的帮助下爬下山。奶牛可能会在山顶暂时聚集,如果它们爬上山后需要等待唐农夫的帮助才能下山。奶牛下山的顺序可以与上山的顺序不同。

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

输入格式 climb.in

第一行,一个整数

到第 行,每行两个用空格隔开的整数

输出格式 climb.out

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

样例

输入 #1

3
6 4
8 1
2 3

输出 #1

17