#2072. [POI2004]MOS

题目描述

一个夜晚一些旅行者想要过桥. 他们只有一个火把. 火把的亮光最多允许两个旅行者同时过桥. 没有火把或者多于2个人则不能过桥.每个旅行者过桥都需要特定的时间, 两个旅行者同时过桥时时间应该算较慢的那个. 我们想知道所有旅行者最少要花费多少时间才能全部过桥? Example 假如有4个人. 他们分别需要花费6,7,10,15分钟过桥.下图演示了他们如何使用44分钟全部过桥的,但他们能做得更快么?

输入格式

第一行一个数n 表示旅行者的总数, 1 <= n <= 100,000. 接下来n 行表示所有旅行者的过桥时间,时间从小到大排列,每个数不超过1,000,000,000.

输出格式

输出一个数表示最少过桥时间.

样例

样例输入

4  

6  

7  

10  

15  

样例输出

42  

数据范围与提示