题目描述

Kile 和 Pogi 在路上捡到了 $N$ 张钞票。他们将分别取走若干张钞票，使得每人所得的总金额相同。同时要尽可能保证分得的总金额最大。

接着，他们会带着剩下的钞票前往赌场。由于他们的运气很好，因此他们将剩余金额作为赌注后，会得到双倍的金额。然后，他们会将得到的金额再次平分，并加入每个人的总金额中。

求每个人能够分得的总金额是多少。

输入格式

第一行，一个整数 $N$。

接下来的 $N$ 行，每行一个正整数 $c_i$，表示第 $i$ 张钞票的面额。保证 $N$ 张钞票的总金额不超过 $10^5$。

输出格式

输出每个人能够分得的总金额。

4
2
3
1
6

6

5
2
3
5
8
13

18

提示

【样例 1 解释】

Kile 可以选择取走面额分别为 $2,3,1$ 的钞票，而 Pogi 可以取走面额为 $6$ 的钞票。由于没有剩余钞票，因此每人所得总金额为 $6$。

【样例 2 解释】

Kile 可以选择取走面额分别为 $5,8$ 的钞票，而 Pogi 可以取走面额为 $13$ 的钞票。剩下的钞票面额分别为 $2,3$，因此在前往赌场之后，每人所得总金额为 $13+2+3=18$。

【数据规模与约定】

对于 $50\%$ 的数据，$N \le 13$。

对于 $70\%$ 的数据，$N \le 50$，$\sum c_i \le 1000$。

对于 $100\%$ 的数据，$1 \le N \le 500$。

【提示与说明】

题目译自 COCI 2016-2017 CONTEST #4 T3 Kas。

本题分值按 COCI 原题设置，满分 $100$。