深夜，一群游客想要穿过一座破旧的桥。他们只有一支火炬。火炬的光亮最多允许两名游客同时过桥。游客过桥时必须携带火炬，且每次过桥的人数不能超过两人，否则他们会掉进河里。每位游客过桥都需要一定的时间。当两名游客一起过桥时，所需时间等于其中较慢的那位游客所需的时间。请问所有游客过桥所需的最短时间是多少？

样例

假设该组共有 4 人。第一人过桥需要 6 分钟，第二人需要 7 分钟，第三人需要 10 分钟，第四人需要 15 分钟。下图展示了他们如何在 44 分钟内过桥。然而，他们可以更快地完成。怎么做呢？

一种在 44 分钟内过桥的假设方法。圆圈中的数字表示每位游客过桥所需的时间（以分钟为单位）。

实现细节

编写一个程序，完成以下任务：

• 从标准输入读取游客组的描述；
• 计算所有游客过桥所需的最短时间；
• 将结果写入标准输出。

输入格式

标准输入的第一行包含一个正整数 $n$，表示游客的人数，$1 \le n \le 100\,000$。接下来的 $n$ 行每行包含一个整数，构成一个非递减序列，且每个数不超过 $1\,000\,000\,000$。第 $(i+1)$ 行的数字（$1 \le i \le n$）表示第 $i$ 位游客过桥所需的时间。这些数字的总和不超过 $1\,000\,000\,000$。

输出格式

你的程序应在标准输出的第一行写入一个整数，即所有游客过桥所需的最短时间。

样例

输入 1

4
6
7
10
15

输出 1

42