题目描述

终于逃脱了魔王,但是祸不单行,阿什尼又遇到了另一个BOSS,同时逃跑到了一个吊桥边,同样这个桥也只能通过两个人,但可喜的是这个桥是比较新的,不需要考虑载重.

!(https://0d077ef9e74d8.cdn.sohucs.com/rpjpKGh_jpg =300x300)

但是天也黑了,这导致了魔王的能力UP$\uparrow \uparrow \uparrow$,如果在没有光源的情况下想通过吊桥就会被魔王吃掉!

万幸,阿什尼有一个手电筒,可能帮助大家过桥.但是这些史莱姆在天黑的情况下变得胆小了,这导致他们的速度下降了,每个史莱姆的速度是不一样的.

所以,如果两个史莱姆一起过桥的时候必须一起走,不然落后的会被吃掉!

!(https://0d077ef9e74d8.cdn.sohucs.com/rpcxbHX_png)

输入格式

• 第一行一个数字$n$,表示史莱姆的个数
• 第二行$n$个数,表示第$i$个史莱姆过桥的时间,时间越大,过桥越慢

输出格式

一个数,所有史莱姆都过桥的最短时间

输入样例

4
1 2 5 10

5
1 2 8 7 6

输出样例

17

22

提示

• 对于$50$, $0\leq n \leq 10$
• 对于$100$, $0\leq n \leq 1000$,时间$\leq 100$

如果两个人一起过桥,按时间慢的那个算
过桥了,还要把手电筒送来,才能让剩下的史莱姆过去呀!