拔河比赛

题目描述

要举办一场拔河比赛，一共有 $n$ 位同学报名参加，这 $n$ 位同学对拔河产生的贡献各不相同。根据指导老师的要求，我们需要将这 $n$ 位同学分为尽可能势均力敌的两组（这两组同学的人数可以不相同），试问贡献值较少的一组的总贡献为多少。

输入格式

第一行输入一个整数 $n$，表示报名参加拔河比赛的学生的人数。

第二行输入 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 位同学所作出的贡献。

输出格式

输出一个整数，表示贡献值之和较少的一组的贡献值之和。

样例 #1

样例输入 #1

5 
1 2 3 4 5

样例输出 #1

7

样例解释

可以将参赛队伍分为 $\{1, 2, 4\}$ 和 $\{3, 5\}$ 两支队伍，由题目可知两支队伍的成员产生的贡献值的差最小，因此答案为 $7$。

数据范围

对于 100% 的数据：

• $1 \leq n \leq 100$
• $1 \leq a_i \leq 200$

测试点分布