远古遗迹中发掘出了 n 件魔力核心，第 i 件核心蕴含的能量为 k_i。为了安全运输，需要将这些核心分配到两个不同的能量舱（记为舱 A 和舱 B）中。每件核心必须整个放入一个舱，不可拆分。

分配完成后，设舱 A 的总能量为 s_A，舱 B 的总能量为 s_B。为了平衡运输风险，希望两个舱中总能量较大的一方尽可能小，即最小化 max(s_A, s_B)。

请你计算这个最小的最大值。

输入格式

第一行，一个整数 n。第二行，n 个整数 k_1, k_2, …, k_n。

输出格式

输出一个整数，表示 max(s_A, s_B) 的最小可能值。

输入样例1

5
2 3 5 10 12

输出样例1

17

输入样例2

6
22 25 26 45 22 31

输出样例2

89

说明提示

2 ≤ n ≤ 20

1 ≤ k_i ≤ 10^8

限制

时间限制：1000ms，内存限制：256MiB