T264125 黑暗能量

 >大家都说黑暗能量是不好的，可是我却不这么认为 > >喜羊羊，黑暗能量是个好东西吧 > >它可以让我们变得更加厉害 > >只要有了这股能量，我就能得到 > >...权利 > >...力量 > >再也...不用在别人面前当小丑了！ > >我... > >要成为这个世界的王！ 

狗国王给了喜羊羊与灰太狼 $n$ 瓶装有黑暗能量的容器，第 $i$ 个容器里装有质量为 $a_i$ 的黑暗能量。 一个容器一旦被打开，里面所装的黑暗能量将会立即被离容器最近的一个人全部吸收，也就是说，一个容器里的**黑暗能量不可分割，只能全部给某一个人**。 拥有黑暗能量的喜羊羊与灰太狼正在大战一场，为了保证公平，喜羊羊和灰太狼必须**分到总质量相同的黑暗能量**。 他们想保证公平的情况下分到尽可能多的黑暗能量，也就是说他们要尽可能多的平分黑暗能量，剩下无法平分的黑暗能量只能放弃使用。 你能帮他们求出，最多可以使用多少质量的黑暗能量吗？

第一行一个正整数 $n$，表示有 $n$ 瓶黑暗能量。 接下来 $n$ 行，每行一个整数 $a_i$，表示第 $i$ 个容器里装有质量为 $a_i$ 的黑暗能量。

一个整数，最多可以使用黑暗能量的质量。

## 样例解释 ### 样例组 #1 喜羊羊获得质量为 $1+4+5$ 的黑暗能量，灰太狼获得质量为 $2+8$ 的黑暗能量，刚好把黑暗能量分完，共获得质量为 $20$ 的黑暗能量。 ### 样例组 #2 喜羊羊获得质量为 $1+3$ 的黑暗能量，灰太狼获得质量为 $2+2$ 的黑暗能量，共获得质量为 $8$ 的黑暗能量。 ## 数据规模与约定 本题共有 $20$ 个测试点。 对于 $50\%$ 的数据，$n \le 13$； 对于 $70\%$ 的数据，$n \le 50$，提供的黑暗能量的总质量不超过 $10^3$； 对于 $100\%$ 的数据，$n \le 500$，提供的黑暗能量的总质量不超过 $10^5$。 注意：对于以上三档数据，每档数据中分别含有 $1$ 个测试点空间限制为 $2$ MB，即总共有 $15\%$ 的测试点空间限制为 $2$ MB，其余测试点空间限制为 $256$ MB。