题目描述

已知一堆魔法石的重量,问如何分成两堆,使得它们质量和之差最大,但不能大于这些数中的最大数。

输入格式

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

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

输出格式

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

样例

输入样例

5
2 4 5 8 10

输出样例

9