14 级直升研究生机考

C. 双塔问题

单点时限: 1.0 sec

内存限制: 256 MB

Alice 和 Bob 在玩积木游戏。

他们找到了 $n$ 块积木,这些积木都是正方体,棱长分别为 $a_1, a_2, \ldots, a_n$。现在 Alice 和 Bob 要用这些积木垒两座高塔。他们想要这两座高塔的高度相等。问最大高度可能是多少?

摆放积木的顺序没有要求。两座高塔不能公用积木。

输入格式

第一行一个整数 $n$ 。

第二行 $n$ 个整数,用空格隔开,分别是 $a_1, a_2, \ldots, a_n$ $(a_i \geq 1, \sum_{i=1}^n a_i \leq 10~000)$。

数据点规模约定:

  • 对于 $30\%$ 的数据,$1 \leq n \leq 15$。
  • 对于 $100\%$ 的数据,$1 \leq n \leq 100$。

输出格式

输出一个整数,表示最大高度。

如果不能完成任务,输出 $0$。

样例

Input
6
2 3 3 3 6 8
Output
11

提示

样例选择 $2,3,3,6,8$ 这五块积木,搭出 $8+3=11$ 和 $6+3+2=11$ 这两座塔。所以答案是 $11$。