D - 烹饪

得分：400分

问题描述

Takahashi要做N道菜，编号为1到N。

菜i需要连续使用烤箱Ti分钟。一个烤箱不能同时用于两个或多个菜。

如果Takahashi有两个烤箱可用，那么烹饪N道菜所需的最短时间是多少？假设除使用烤箱之外的所有过程都可以忽略不计。

约束条件

• $1 \leq N \leq 100$
• $1 \leq T_i \leq 10^3$
• 所有输入的值都是整数。

输入

输入的格式如下：

N
T_1 ... T_N

输出

输出答案。

输入样例

5
8 3 7 2 5

输出样例

13

我们可以使用两个烤箱按照以下方式在13分钟内烹饪所有菜肴。

• 第一个烤箱：按照顺序烹饪菜肴5和1。
• 第二个烤箱：按照顺序烹饪菜肴2，4和3。

输入样例2

2
1000 1

输出样例2

1000

输入样例3

9
3 14 15 9 26 5 35 89 79

输出样例3

138