You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1623 题。

题目描述

现在有 $n$ 个苹果，苹果的重量分别为 $a_1,a_2,\cdots,a_n$。你的任务是将苹果分成两堆，使得两堆苹果的重量和的差值最小。

输入格式

第一行输入一个正整数 $n$ 表示苹果数量。

第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每一个苹果的重量。

输出格式

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

样例

5
3 2 7 4 1

1

说明/提示

样例解释

可以分成重量为 $(2,3,4)$ 和 $(1,7)$ 的两堆，这样重量和的差值为 $(2+3+4)-(1+7)=1$，可以证明这种划分方式重量和的差值是最小的。

数据范围

$1\le n \le 20,1\le a_i \le 10^9$。