烹饪

题目描述

高桥君准备烹饪 $N$ 道菜，称为菜 1 到菜 $N$。

菜 $i$ 可以用烤箱连续烤 $T_i$ 分钟。一个烤箱不能同时用于两道或更多道菜。

如果高桥君有两个烤箱可用，烹饪完所有 $N$ 道菜所需的最短时间是多少分钟？假设除使用烤箱以外的所有过程耗时忽略不计。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

5
8 3 7 2 5

13

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

第一个烤箱：依次烹饪菜 5 和 1。

第二个烤箱：依次烹饪菜 2、4 和 3。

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$
• 输入均为整数