题目描述

有 $N$ ( $1 \le N \le 250$ )块宝物，第 $i$ 块宝物的价值是 $v_i$ ( $1 \le V_i \le 2,000$ )。现在要把这 $N$ 块宝物分成两堆，使得这两堆的价值的差距最小。因为可能有多种方案使得分开后的两堆宝物的价值差距最小？

例如有 5 块宝物，价值分别是: 2, 1, 8, 4, 16. 那么其中一堆是： 1+2+4+8=15，另外一堆只有价值是 16 的宝物，那么这两堆的差距是 16-15=1. 这是最优方案了。

输入格式

第 $1$ 行: 一个整数 $N$ 。

第 $2$~$N+1$ 行: 每行一个整数，表示一块宝物的价值。

输出格式

一个整数，表示分开后的两堆宝物的价值的最小差距。

样例

5
2
1
8
4
16

1