过桥

来源

ZOJ Monthly, April 2003 (ZOJ1579)

题目描述

有一家人，共N人，要在晚上过一座桥。由于天非常黑，他们提着一盏灯过桥。不幸的是，桥很窄，因此同一时刻最多允许两人同时过桥，而且过桥时必须提着灯。每个人过桥的速度不一样，而且两个人同时过桥时只能以两者的速度中较小的速度过桥。问题是，给定家庭的人数N，以及每个人单独过桥所需的时间，求整个家庭全部通过桥所需的最少时间。

输入描述

输入文件中包含多个测试数据。每个测试数据占2行：第1行位一个整数N，满足0≤N≤100000；第2行，给定了N个整数，为每个人单独过桥时所需的时间。

输出描述

对每个测试数据，输出一行，为整个家庭全部通过桥所需的最少时间。

样例输入

5
1 3 6 8 12
3
7 8 9

样例输出

29
24