题目描述

由于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\)
• 所有输入值均为整数。