题目描述

有 $n$ 个人要过桥，只有一个手电筒。每次最多两人同行，过桥必须携带手电筒，两人同行时用时为较慢者的时间。手电筒需要由人带回，不能抛掷。求所有人到达对岸所需的最短时间。

输入格式

第一行整数 $n$。接下来 $n$ 行，每行一个人的过桥时间。

输出格式

输出最短总时间。

样例

4
1
2
5
10

17

数据范围

对于40%的数据，$n\le100$；对于100%的数据，$1\le n\le1000$，每人过桥时间为 $1$ 至 $100$ 的整数。