问题描述

$N$ 个部门，部门 $i$ 有 $K_i$ 人。你需要将其分成 A/B 两组，最小化 $\max(S_A, S_B)$。

其中 $S_A$ 表示第一组的人数之和，$S_B$ 表示第二组的人数之和。

输入格式

第一行输入一个正整数 $N$。

第二行输入 $N$ 个整数 $K_i$。

输出格式

一个整数。

样例输入 1

5
2 3 5 10 12

样例输出 1

17

样例输入 2

2
1 1

样例输出 2

1

样例输入 3

6
22 25 26 45 22 31

样例输出 3

89

评测数据规模

对于 $100\%$ 的数据，$2 \le N \le 20$，$1 \le K_i \le 10^8$。