我--过桥

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

n个人要过一座桥,只是在漆黑的夜里,没有火把显然是不行的。但是这n个人只有一个火把,并且这座桥每次最多只能通过两个人。
每个人的速度不同,若两人组队,队伍速度等于较慢一人的速度。你要做的是计算这n个人全部通过这座桥的最少时间。

Input

多组输入。每组数据的第一行是输入一个n,代表有n(1 <= n && n <= 500)个人,接下来的n个整数,代表着每个人穿过这座桥所需要的时间。

Output

输出一个整数,代表最优策略所需时间。

Sample Input

4
1
10
5
2

Sample Output

17

Hint

假设人员编号按输入顺序从1到n,首先编号为1,4的人通过,编号为1的回来送火把,然后编号为2,3组队通过,编号为4的回来送火把,编号为1,4通过,结束。
Sum = 2 + 1 + 10 + 2 + 2 = 17。

Source