1682: 过桥问题

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：5 解决：4

题目描述

在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

输入

第一行输入一个整数N

第二行输入N个整数，表示N个人过桥需要的时间

输出

输出一行，包含一个整数，表示所有人过桥需要的最少时间

样例输入 复制 

5
1 3 6 8 12

样例输出 复制 

29

提示

1 3一起过桥，花费时间3

3回来，花费时间3

8 12一起过桥，花费时间12

1回来，花费时间1

1 6一起过桥，花费时间6

1 回来，花费时间1

1 3一起过桥，花费时间3

一共花费3 + 3 + 12 + 1 + 6 + 1 + 3 = 29分钟