题目描述

随着莆田一中总部员工人数的增加，学校决定将总部的各个部门分成两组，并错开它们的中午休息时间。

莆田一中总部有N个部门，每个部门的人数为$K_i$（1 ≤ i ≤ N）。为了确保两个组的中午休息时间不重叠，需要将各个部门分配到组A或组B，且每组的休息时间完全错开。

请你找到最优的分配方式，使得两个组中午休息时的人数差尽可能小。换句话说，找到以下较大者的最小值：分配给组A的部门总人数和分配给组B的部门总人数中的较大值。

约束

• 2≤N≤100
• 1≤$K_i$≤$10^4$
• 所有输入值均为整数。

输入

输入来自标准输入，格式如下：

N
K1 K2 …… KN

输出

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

样本输入 1

5
2 3 5 10 12

示例输出 1

17

解释：

在这个例子中，部门人数分别为2, 3, 5, 10, 12。通过合理的分组，最优分配为：

• 组A：部门1、部门2和部门5，人数总和为2 + 3 + 12 = 17。
• 组B：部门3和部门4，人数总和为5 + 10 = 15。

组A和组B的最大人数分别为17和15，因此输出max(17, 15) = 17。显然，无法将部门分配成两个组，使得两组的最大人数为16或更少，所以输出17。

样本输入 2

2
1 1

样本输出 2

1

样本输入 3

6
22 25 26 45 22 31

样本输出 3

89

数据范围

对于全部数据，有 2≤N≤100, 1≤$K_i$≤$10^4$。