错峰午餐

题目描述

随着 KEYENCE 总部的员工越来越多，他们决定把总部的各部门分成两组，错开午休时间。

KEYENCE 总部有 $N$ 个部门，第 $i$ 个部门（$1 \le i \le N$）的人数为 $K_i$。

在把每个部门分配到 A 组或 B 组、让两组各自同时午休，并保证 A 组与 B 组的午休时间不重叠的前提下，求同一时间午休的最大人数的最小可能值。

换言之，求「分配到 A 组的部门人数总和」与「分配到 B 组的部门人数总和」中较大者的最小可能值。

输入格式

输入按以下格式从标准输入给出：

$N$
$K_1$ $K_2$ $\ldots$ $K_N$

输出格式

输出同一时间午休的最大人数的最小可能值。

样例

5
2 3 5 10 12

17

将部门 $1$、$2$、$5$ 分到 A 组，部门 $3$、$4$ 分到 B 组时，A 组共有 $2+3+12=17$ 人，B 组共有 $5+10=15$ 人，因此同一时间午休的最大人数为 $17$。

无法让两组成员数都不超过 $16$ 人，因此输出 $17$。

2
1 1

1

可能有多个部门人数相同。

6
22 25 26 45 22 31

89

例如，将部门 $1$、$4$、$5$ 分到 A 组，部门 $2$、$3$、$6$ 分到 B 组时，同一时间午休的最大人数为 $89$。

数据范围

• $2 \le N \le 20$
• $1 \le K_i \le 10^8$
• 所有输入均为整数