You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

输入格式

第一行输入一个整数 $n (1 \le n \le 1000)$，表示有 n 个小朋友。

第二行有 n 个整数 $a_i$，$a_i$表示第 i 个小朋友过河需要的时间$（0 < a_i \le 1000）$。

输出格式

输出一个整数，表示所有小朋友过河所需要的时间。

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 bridge.in，输出文件为 bridge.out

样例输入

4
1 2 5 10

样例输出

17