J16 习题-9 分钱

题目描述

佩奇和乔治在街上捡到了恶魔掉的 $N$ 张钞票，他们准备这些将钞票平分。他们想得到相同的金额。但是有时候，无论怎么分都无法平均分配，总会剩下一部分。 现在，他们已经尽可能的分配更多的钱，然而剩余的部分钞票没有办法平分了，他们又不想将剩下的部分钞票留在街上，他们决定去附近的赌场将剩下的钞票押上，希望得到两倍的赌注。幸运的是真的实现了，有了这些赌注，佩奇和乔治就可以平分了所有钞票。 现在请问，他们每人获得了多少钱。

输入格式

第一行一个整数 $N$，表示钞票的数量。 接下来 $N$ 行，每行一个整数，表示每张钞票的金额。

输出格式

一个整数，表示最后每人获得的金额。

样例输入1

4
2
3
1
6

样例输出1

6

样例1分析

佩奇拿走金额为 $2,3,1$ 的钞票，乔治拿走金额为 $6$ 的钞票。

样例输入2

5
2
3
5
8
13

样例输出2

18

样例2分析

佩奇拿走金额 $5,8$ 的钞票，乔治拿走金额 $13$ 的钞票。剩下的钞票金额为 $2,3$ ，用剩下的金额在赌场翻倍。他们每个人的总收入为 $13 + 5 = 18$。

数据范围

对于$50\%$的数据，$N \leqslant 13$； 对于$70\%$的数据，$N \leqslant 50$，钞票的总金额不超过 $10^3$； 对于$100\%$的数据，$N\leqslant 500$，钞票的总金额不超过 $10^5$。