AT_abc374_c [ABC374C] Separated Lunch

由于 Keyence 总公司的员工人数不断增加，公司决定将总部的所有部门分成两组，并分别安排不同的午休时间段。 Keyence 总公司共有 $N$ 个部门，第 $i$ 个部门有 $K_i$ 人。 请将每个部门分配到组 $A$ 或组 $B$ 中，使得每组的部门可以同时午休，并且组 $A$ 和组 $B$ 的午休时间不重叠。请你求出在所有可能的分组方式中，同时午休的最大人数的最小可能值。 也就是说，设组 $A$ 的总人数为 $S_A$，组 $B$ 的总人数为 $S_B$，请你最小化 $\max(S_A, S_B)$。

输入通过标准输入给出，格式如下： > $N$ $K_1$ $K_2$ $\ldots$ $K_N$

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

## 限制条件 - $2 \leq N \leq 20$ - $1 \leq K_i \leq 10^8$ - 所有输入均为整数 ## 样例解释 1 将第 $1,2,5$ 个部门分配到组 $A$，第 $3,4$ 个部门分配到组 $B$ 时，组 $A$ 的总人数为 $2+3+12=17$，组 $B$ 的总人数为 $5+10=15$，此时同时午休的最大人数为 $17$。 无法将部门分配得使得组 $A$ 和组 $B$ 的总人数都不超过 $16$，因此输出 $17$。 ## 样例解释 2 可能存在多个部门人数相同的情况。 ## 样例解释 3 例如，将第 $1,4,5$ 个部门分配到组 $A$，第 $2,3,6$ 个部门分配到组 $B$ 时，同时午休的最大人数为 $89$。 由 ChatGPT 4.1 翻译