【题目描述】

某中学体育场上原先只有一块场地用于学生上课时自由活动,但是由于人数过多，学校另外开发了一块新的场地供学生上课时自由活动时使用。

该学校在同一时刻共有 $N$ 个班级上体育课，第 $i$ 个班的总人数为 $K_i$,课间活动时由于所有学生都想去新场地,但是新场地是无法容纳所有人的,且两块场地人数差距越大,冲突值就越大,这不是学校所希望看到的,因此学校需要提前分配好每个班级所在区域,尽可能减少冲突。

要求不能拆分任何一个班级，每个班必须完整分配到新场地或者旧场地上。分组完成后，每块场地的总人数为该场地班级人数之和。

我们要找到所有合法分组方案中，冲突值最小的方案，输出该方案下两块场地总人数最多的那块场地的人数

【输入格式】

第一行一个正整数 $N$，代表全校的班级总数。

第二行 $N$ 个用空格隔开的整数 $K_1,K_2,\dots,K_N$，分别代表每个班级的总人数。

【输出格式】

输出一行一个整数, 即冲突值最小时，两块场地总人数最多的那块场地的人数

【样例 1】

5
2 3 5 10 12

17

【样例 1 解释】

最优方案为:

把 $1,2,5$ 号班分到第 $1$ 组总人数是 $2+3+12=17$

把 $3,4$ 号班分到第 $2$ 组总人数是 $5+10=15$

此时冲突值为 $2$, 人数最多为 $17$。

【样例 2】

2
1 1

1

【样例 2 解释】

两个班各分到不同批次，冲突值为 $0$ , 人数最多为 $1$。

【数据规模与约定】

对于全部的测试点，保证：

• $2 \le N \le 20$
• $1 \le K_i \le 10^8$