BZPRO
#2072. [POI2004]MOS
内存限制：64 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
一个夜晚一些旅行者想要过桥. 他们只有一个火把. 火把的亮光最多允许两个旅行者同时过桥. 没有火把或者多于2个人则不能过桥.每个旅行者过桥都需要特定的时间, 两个旅行者同时过桥时时间应该算较慢的那个. 我们想知道所有旅行者最少要花费多少时间才能全部过桥? Example 假如有4个人. 他们分别需要花费6,7,10,15分钟过桥.下图演示了他们如何使用44分钟全部过桥的,但他们能做得更快么?
输入格式
第一行一个数n 表示旅行者的总数, 1 <= n <= 100,000. 接下来n 行表示所有旅行者的过桥时间,时间从小到大排列,每个数不超过1,000,000,000.
输出格式
输出一个数表示最少过桥时间.
样例
样例输入
4
6
7
10
15
样例输出
42
数据范围与提示
BZPRO