Ante 和 Goran 正在为来自萨格勒布大学的学生程序设计竞赛培训 $N$ 支由充满抱负的年轻学生组成的队伍。他们两人每人都有一个算法需要向每支队伍讲解。当然，他们两人不能同时指导同一支队伍，且他们中任何一人都不能同时指导多支队伍。

给定每支队伍理解并实现一个算法所需的时间。每次算法讲解必须不间断地进行。求 Ante 和 Goran 完成所有讲解所需的最短时间！

更多解释请参考样例说明。

输入格式

第一行包含一个整数 $N$，表示队伍的数量。

第二行包含 $N$ 个空格分隔的整数，其中第 $i$ 个整数表示第 $i$ 支队伍理解并实现一个算法所需的时间。

输入中的所有数字均在区间 $[1, 3 \cdot 10^5]$ 内。

输出格式

输出的第一行也是唯一一行，应包含题目所求的最小时间。

子任务

在占总分 40% 的测试数据中，满足 $N \le 7$。

样例

输入样例 1

3
2 2 2

输出样例 1

6

输入样例 2

3
4 1 2

输出样例 2

8

输入样例 3

4
1 3 2 1

输出样例 3

7

说明

样例 1 说明：每支队伍需要 2 个单位的时间来理解和实现算法。一种可能的安排是：Ante 依次向队伍 1、队伍 2 和队伍 3 讲解，而 Goran 依次向队伍 3、队伍 1 和队伍 2 讲解。

样例 2 说明：一种最优的安排是：Ante 依次向队伍 2、队伍 3 和队伍 1 讲解，但在向队伍 3 和队伍 1 讲解之间暂停 1 个单位的时间。Goran 则依次向队伍 1、队伍 3 和队伍 2 讲解。