Score : $400$ points

问题陈述

高桥打算烹饪 $N$ 道菜肴，分别命名为第 1 道至第 $N$ 道菜肴。

第 $i$ 道菜肴需要连续使用烤箱 $T_i$ 分钟才能完成。同一时间，烤箱不能用于烹制两道或更多菜肴。

如果高桥有两台烤箱可用，那么他最少需要多少分钟来烹制完全部 $N$ 道菜肴？假设除了使用烤箱之外的所有过程所花费的时间均可忽略不计。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi is going to cook $N$ dishes called Dish $1$ through $N$.

Dish $i$ can be cooked by using an oven for $T_i$ consecutive minutes. An oven cannot be used for two or more dishes simultaneously.

If Takahashi has two ovens to use, what is the shortest number of minutes needed to cook all the $N$ dishes? Assume that all processes other than using ovens take negligible time.

Constraints

• $1 \leq N \leq 100$
• $1 \leq T_i \leq 10^3$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$T_1$ $\ldots$ $T_N$

Output

Print the answer.

Sample Input 1

5
8 3 7 2 5

Sample Output 1

13

We can, for example, use the two ovens as follows to cook all the dishes in $13$ minutes.

• The first oven: Cook Dishes $5$ and $1$ in this order.
• The second oven: Cook Dishes $2$, $4$, and $3$ in this order.

Sample Input 2

2
1000 1

Sample Output 2

1000

Sample Input 3

9
3 14 15 9 26 5 35 89 79

Sample Output 3

138

update @ 2024/3/10 09:17:23