题目描述

由于KEYENCE 总部的员工越来越多，他们决定将总部各部门分成两组，错开午休时间。

KEYENCE 总部有$N$个部门，而第$i$个部门($1≤i≤N$)的人数为$K_i$。

将每个部门分配到$A$组或$B$组让每个组在同一时间午休，并确保$A$组和$B$组的午休时间不重叠，求同一时间午休的最大人数的最小值。换句话说，求分配给$A$组的部门总人数和分配给$B$组的部门总人数中较大者的最小值。

输入格式

输入内容由标准输入法提供，格式如下

$N$

$K_1$ $K_2$ $…$ $K_N$

输出格式

打印最多同时午休人数的最小值。

样例 #1

样例输入 #1

5
2 3 5 10 12

样例输出 #1

17

样例 #2

样例输入 #2

2
1 1

样例输出 #2

1

样例 #3

样例输入 #3

6
22 25 26 45 22 31

样例输出 #3

89

提示

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