题目描述

在漆黑的夜里，$N$ 位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒，大家无论如何也不敢过桥。

不幸的是，$N$ 个人一共只带了一只手电筒，而桥窄得只够让两个人同时通过。如果一个人单独过桥，所需时间已知；如果两个人同时过桥，所需时间等于走得较慢的那个人单独过桥所需时间。

请设计一个方案，让这 $N$ 个人尽快全部过桥，并输出最短过桥时间。

例如，有四个人甲、乙、丙、丁，过桥时间分别为 $1,2,5,10$。

一种方案是：甲乙过去（$2$ 分钟），甲回来（$1$ 分钟），甲丙过去（$5$ 分钟），甲回来（$1$ 分钟），甲丁过去（$10$ 分钟），总共 $19$ 分钟。

更优方案是：甲乙过去（$2$ 分钟），甲回来（$1$ 分钟），丙丁过去（$10$ 分钟），乙回来（$2$ 分钟），甲乙再过去（$2$ 分钟），总共 $17$ 分钟。

输入格式

第一行输入一个整数 $N$，表示共有 $N$ 个人要过桥。

第二行输入 $N$ 个整数 $S_i$，表示这 $N$ 个人单独过桥所需时间。

输出格式

输出一个整数，表示所有人过桥的最短时间。

样例

4
1 2 5 10

17

数据范围

$1 \le N \le 1000$，$0 < S_i \le 100$。

来源

贪心