← 返回题目列表

AtCoder · abc204_d

D. 烹饪

中文机器翻译题面 查看原题

分数: 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