储蓄罐
小明和佳佳打破了他们共同积攒的储蓄罐，里面有各种各样的零钱，共有N张纸币。现在，他们两人想要尽可能的平分这些纸币，但是纸币上的面值可能各不相同，他们想尽了办法，决定先求得最多能分成的两份面值总和相同的纸币。
再将剩下无法平分的纸币总和x，由妈妈再出一份相同的份额x，那么，他们就可以得到同样的总钱数。
现在妈妈请你算一下，在妈妈出钱最少的情况下，小明和佳佳分别能得到多少总钱数。
输入
第一行一个整数N，表示有N张纸币。
接下来N行，每行一个整数，表示每张纸币的面值，面值总和不会超过100000
输出
输出他们两人分别可以得到的总钱数。
样例输入
4
2
3
1
6
5
2
3
5
8
13
样例输出
6
18
提示
【样例解释1】
4张纸币，刚好可以分成1+2+3=6，平分两份，妈妈就不用再出钱了，两人分别得到6元。
【样例解释2】
5张纸币，最多可以得到5+8=13，剩下的2和3无法再平分，妈妈再出5元，这样两人可以得到13+5=18元
【数据范围】
50%的测试数据，N不会超过13。
70%的测试数据，N不会超过50，总钱数不会超过1000。
100%的测试数据，N不会超过500，总钱数不会超过100000。
用dp怎么做
