题目描述

有 $n$ 个苹果，每个苹果有已知的重量。你的任务是将苹果分成两组，使得两组重量之差最小。

输入格式

第一行包含一个整数 $n$：苹果的数量。

第二行包含 $n$ 个整数 $p_1,p_2,\dots,p_n$：每个苹果的重量。

输出格式

输出一个整数：两组重量的最小差值。

5
3 2 7 4 1

1

提示

第一组重量为 $2,3,4$（总重 $9$），第二组重量为 $1,7$（总重 $8$）。

数据范围与提示

$1 \le n \le 20$ $1 \le p_i \le 10^9$