[COCI2016-2017#4] Kas

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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf) _T3 Kas_。** **本题分值按 COCI 原题设置，满分 $100$。**