分数: 400 点
问题陈述
高桥要做饭了 N 菜品叫Dish 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