题目描述

在一个夜黑风高的晚上，有n个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，

所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

输入格式

第一行输入一个整数n

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


1 ≤ 所有的数 ≤ 1000

输出格式

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

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分钟