题目描述

在漆黑的夜里，N位旅行者来到了一座狭窄且没有护栏的桥边。若不借助手电筒，所有人都无法安全过桥。

不幸的是，N人仅携带了一只手电筒，且桥窄到只能容纳两人同时通过。已知每个人单独过桥所需的时间；若两人同时过桥，所需时间则为两人中单独过桥时间较慢者的用时。

请设计一个方案，计算让这N人全部过桥的最短时间。

例如，有甲、乙、丙、丁四位旅行者，他们单独过桥的时间分别为1、2、5、10（单位：分钟）：

• 方案一：最快的两人先过桥，再由最快者往返接送剩余的人。流程为：甲乙过桥（2分钟）→ 甲返回（1分钟）→ 甲丙过桥（5分钟）→ 甲返回（1分钟）→ 甲丁过桥（10分钟），总耗时19分钟。
• 方案二：让最慢的两人一起过桥，减少慢者过桥次数。流程为：甲乙过桥（2分钟）→ 甲返回（1分钟）→ 丙丁过桥（10分钟）→ 乙返回（2分钟）→ 甲乙过桥（2分钟），总耗时17分钟。

最终，四人过桥的最短时间为17分钟。

输入格式

1. 第一行一个整数N（1 ≤ N ≤ 1000），表示旅行者的人数。
2. 第二行包含N个整数Si（0 < Si ≤ 100），依次表示每个人单独过桥所需的时间。

输出格式

一行一个整数，表示所有旅行者过桥的最短时间。

输入输出样例

输入样例1

4
1 2 5 10

输出样例1

17