题目描述

Y 同学有 $N$ 块砝码，第 $i$ 块重量为 $A_i$ 。他要把所有砝码分到左右两个托盘中，每块砝码必须且只能放入一个托盘。

请你求出两个托盘总重量差的最小可能值。

输入格式

第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数 $A_1,A_2,\dots,A_N$ 。

输出一行一个整数，表示最小重量差。

5
3 1 4 2 2

对于 $100\%$ 的数据，保证 $1\le N\le5000$ ， $1\le A_i\le1000$ ，且 $\sum A_i\le2\times10^5$ 。

测试点编号	分值	$N\le$	$\sum A_i\le$	特殊性质
$1\sim4$	$16$	$30$	$300$	无
$5\sim8$	$16$	$5000$	$2\times10^5$	特殊性质 A
$9\sim12$	$18$	$5000$	$5\times10^4$	特殊性质 B
$13\sim16$	$20$	$1000$	$10^5$	无
$17\sim22$	$30$	$5000$	$2\times10^5$	无

特殊性质 A：保证所有 $A_i$ 相等。

特殊性质 B：保证 $A_i\le10$ 。