时间限制： 1.0 秒

空间限制： 256 MB

题目描述

Alice 和 Bob 在玩积木游戏。

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

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

输入格式

从标准输入读入数据。

第一行一个整数 $n$。

第二行 $n$ 个整数，用空格隔开，分别是 $a_{1} , a_{2} , \ldots , a_{n}$。

输出格式

输出到标准输出。

输出一个整数，表示最大高度。如果不能完成任务，输出 $0$。

6
2 3 3 3 6 8

11

样例 1 解释

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

子任务

对于 $30 \%$ 的数据，$1 \leq n \leq 15$。

对于 $100 \%$ 的数据，$1 \leq n \leq 100,a_i\ge 1,\sum\limits_{i=1}^n a_i\le 10^4$。