题目描述

随着公司规模的扩大，某公司决定对多个部门实施错峰午休制度。

小y的任务是设计一个分组方案，将公司的 $n$ 个部门分配到 $A$ 组或者 $B$ 组，使得每个组内的员工在同一时间午休。每个部门的员工数量由 $nums_i$ 表示。

目标是找到一种分配方式，需要计算出在满足上述条件的情况下，任何一个组中员工总数的最大人数的 最小值。

• $2\leq\ N\ \leq\ 20$
• $1\leq\ num_i\ \leq\ 10^8$

输入格式

$N$

$K_1$ $K_2$ $\ldots$ $num_N$

输出格式

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

5
2 3 5 10 12

17

2
1 1

1

6
22 25 26 45 22 31

89

提示

示例解释 1

• 1, 2, 5 部门分配到 $A$ 组
  • 总人数：2+3+12=17
• 3, 4 部门分配到 $B$ 组
  • 总人数：5+10=15
  • 因此输出为17。