高桥君打算制作从 $1$ 到 $N$ 的 $N$ 道菜。

第 $i$ 道菜需要连续使用烤箱 $T_i$ 分钟来完成。一个烤箱在同一时刻不能同时用于两道或以上的菜。

如果可以使用两个烤箱，制作完所有 $N$ 道菜所需的最短时间是多少？此外，除了使用烤箱的时间外，其他时间可以忽略不计。

输入格式

输入以以下格式从标准输入中给出。

$N$ $T_1$ $T_2$ $\ldots$ $T_N$

输出格式

请输出答案。

5
8 3 7 2 5

13

2
1000 1

1000

9
3 14 15 9 26 5 35 89 79

138

说明/提示

限制条件

• $1 \leq N \leq 100$
• $1 \leq T_i \leq 10^3$
• 输入中的所有值均为整数

样例解释 1

例如，可以如下使用两个烤箱，在 $13$ 分钟内完成所有菜品。

• 第一个烤箱：依次制作菜 $5, 1$。
• 第二个烤箱：依次制作菜 $2, 4, 3$。