题目描述

高桥要烹饪 $N$ 道菜，编号从 $1$ 到 $N$。

第 $i$ 道菜需要使用烤箱连续 $T_i$ 分钟。一个烤箱不能同时用来烹饪两道或更多的菜。

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

约束条件

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

输入

从标准输入读入数据，输入格式如下：

$N$ $T_1 \ldots T_N$

输出

输出答案。

示例输入1

5
8 3 7 2 5

示例输出1

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