该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

漂亮的学姐要做 $N$ 道菜，从 $1$ 到 $N$ ，使用烤箱可以连续 $T_i$ 分钟烹饪 $i$ 道菜，烤箱不能同时烹饪两道或更多菜肴，但是学姐有两个烤箱可以使用，所以现在可以同时使用两个烤箱，假设除使用烤箱以外的所有过程所花费的时间都可以忽略不计

那么烹制所有 $N$ 道菜所需的最短分钟数是多少？

输入格式

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

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

输出格式

一行一个整数，输出答案

样例

5
8 3 7 2 5

13

9
3 14 15 9 26 5 35 89 79

138

样例一解释： 例如，我们可以如下使用两个烤箱，在 $13$ 分钟内烹饪所有菜肴。

• 第一个烤箱依次烹饪菜肴 $5$ 和 $1$ 。
• 第二个烤箱依次烹饪菜肴 $2$ 、 $4$ 和 $3$ 。