题目描述

Ural 1005

给出一堆魔法石的重量,问如何分成两堆,使得它们质量和之差最小,求出这个最小值。

输入格式

第一行一个数$\red{n}$。$\red{(n≤}$$\red{30)}$

接下来$\red{n}$行,每行一个正整数。$\red{( }$每个数$\red{≤}$$\red{100000)}$

输出格式

一个整数表示两组数字和的最小差。

样例

输入样例1

5
1 2 3 4 5

输出样例1

1

输入样例2

5
5 8 13 27 14

输出样例2

3