302007 - 数字分组1

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

Input

第一行一个数n。

接下来n行，每行一个正整数（每个数不大于100000）。

Output

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

Examples

Input

5
1 2 3 4 5

Output

1

Input

5
5 8 13 27 14

Output

3

Hint

1\leq n\leq30

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题