Cooking

题目描述

Takahashi 将要烹饪 $N$ 道菜，称为菜品 $1$ 到 $N$。 菜品 $i$ 可以通过使用烤箱连续 $T_i$ 分钟来烹饪。一个烤箱不能同时用于两个或更多菜品。 如果 Takahashi 有两个烤箱可以使用，烹饪完所有 $N$ 道菜所需的最短分钟数是多少？假设除使用烤箱以外的所有过程所需时间可忽略不计。

输入格式

输入按如下格式由标准输入提供： $N$ $T_1$ $\ldots$ $T_N$

输出格式

输出答案。

5
8 3 7 2 5

13

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$ 输入中的所有数值都是整数。例如，我们可以按如下方式使用两个烤箱在 $13$ 分钟内烹饪完所有菜品。

第一个烤箱：按顺序烹饪菜品 $5$ 和 $1$。 第二个烤箱：按顺序烹饪菜品 $2$、$4$ 和 $3$。

标签: AtCoder|abc204D

来源

AtCoder|abc204D