Score : $300$ points

问题陈述

随着基恩士总部的员工越来越多，他们决定将总部的部门分成两组，并错开他们的午餐时间。

基恩士总部有 $N$ 个部门，第 $i$ 个部门的人数为 $K_i$（$1\leq i\leq N$）。

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

以上为大语言模型 kimi 翻译，仅供参考。

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$.