103742: [Atcoder]ABC374 C - Separated Lunch

Problem Statement

As KEYENCE headquarters have more and more workers, they decided to divide the departments in the headquarters into two groups and stagger their lunch breaks.

KEYENCE headquarters have $N$ departments, and the number of people in the $i$-th department $(1\leq i\leq N)$ is $K_i$.

When assigning each department to Group $A$ or Group $B$, having each group take lunch breaks at the same time, and ensuring that the lunch break times of Group $A$ and Group $B$ do not overlap, find the minimum possible value of the maximum number of people taking a lunch break at the same time.
In other words, find the minimum possible value of the larger of the following: the total number of people in departments assigned to Group $A$, and the total number of people in departments assigned to Group $B$.

Constraints

• $2 \leq N \leq 20$
• $1 \leq K_i \leq 10^8$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the minimum possible value of the maximum number of people taking a lunch break at the same time.

Sample Input 1

5
2 3 5 10 12

Sample Output 1

17

When assigning departments $1$, $2$, and $5$ to Group $A$, and departments $3$ and $4$ to Group $B$, Group $A$ has a total of $2+3+12=17$ people, and Group $B$ has a total of $5+10=15$ people. Thus, the maximum number of people taking a lunch break at the same time is $17$.

It is impossible to assign the departments so that both groups have $16$ or fewer people, so print $17$.

Sample Input 2

2
1 1

Sample Output 2

1

Multiple departments may have the same number of people.

Sample Input 3

6
22 25 26 45 22 31

Sample Output 3

89

For example, when assigning departments $1$, $4$, and $5$ to Group $A$, and departments $2$, $3$, and $6$ to Group $B$, the maximum number of people taking a lunch break at the same time is $89$.

问题陈述

随着KEYENCE总部员工的越来越多，他们决定将总部的部门分为两组，并错开他们的午餐休息时间。

KEYENCE总部有N个部门，第i个部门（1≤i≤N）的人数是K_i。

在将每个部门分配给A组或B组时，让每个组同时进行午餐休息，并确保A组和B组的午餐休息时间不重叠，找出同时进行午餐休息的人数的最小可能最大值。
换句话说，找出以下两者中的较大值的最小可能值：分配给A组的部门的总人数，以及分配给B组的部门的总人数。

约束条件

• 2 ≤ N ≤ 20
• 1 ≤ K_i ≤ 10^8
• 所有输入值都是整数。

输入

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

N
K_1 K_2 … K_N

输出

打印同时进行午餐休息的人数的最小可能最大值。

样本输入1

5
2 3 5 10 12

样本输出1

17

当将部门1、2和5分配给A组，部门3和4分配给B组时，A组总共有2+3+12=17人，B组总共有5+10=15人。因此，同时进行午餐休息的人数最大值为17。

无法分配部门使得两组都有16人或更少，所以打印17。

样本输入2

2
1 1

样本输出2

1

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

样本输入3

6
22 25 26 45 22 31

样本输出3

89

例如，当将部门1、4和5分配给A组，部门2、3和6分配给B组时，同时进行午餐休息的人数最大值为89。