#473. 过河

过河

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

输入格式

第一行输入一个整数 n(1n1000)n (1≤n≤1000) ,表示有 nn 个小朋友。

第二行有 nn 个整数 aia_iaia_i 表示第 ii 个小朋友过河需要的时间0<ai1000(0<a_i≤1000)

输出格式

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

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

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

样例输入

4
1 2 5 10

样例输出

17