题目描述

一群$N$个旅行者（$1 \leq N \leq 50$）来到一座破旧的桥前，希望尽快过河。然而，桥上每次最多只能有两个人。此外，安全过桥需要用手电筒照明，但团队只有一个手电筒。

每个旅行者过桥需要$t_i$秒（$i=1, \ldots, N$，$t_i$为$1$到$100$的整数）。如果两人一起过桥，他们的过桥时间为较慢者的时间。

任务是确定整个团队过桥的最短时间。

输入

输入由两行组成：第一行包含$N$的值，第二行包含$t_i$的值（由一个或多个空格分隔）。

输出

输出包含一行，为结果。

输入数据示例

4  
6 7 6 5  

输出数据示例

29  

来源

2001年东北欧地区赛，西部赛区