题目描述

小可需要打印 $n$ 份文件，文件编号为 $1$ 到 $n$。

第 $i$ 份文件必须连续打印 $t_i$ 分钟。一台打印机在同一时刻只能打印一份文件。

如果可以使用两台打印机，打印完所有 $n$ 份文件所需的最短时间是多少分钟？

除了打印时间之外，文件传输、开关机等时间可以忽略不计。

输入格式

第一行一个整数 $n$，表示文件数量。

第二行 $n$ 个整数 $t_i$，表示第 $i$ 份文件打印所需的时间。

输出格式

输出一个整数，表示打印完所有文件所需的最短时间（分钟）。

样例

5
8 3 7 2 5

13

2
1000 1

1000

9
3 14 15 9 26 5 35 89 79

138

样例1解释

第一个打印机：依次打印 $5$，$1$。

第二个打印机：依次打印 $2$，$4$，$3$。

总共 $13$ 分钟。

数据范围

对于 $30\%$ 的数据，$1\le n\le 20$。

对于 $100\%$ 的数据，$1 \le n \le 100$，$1 \le t_i \le 1000$。