题目描述

给出n(1≤n≤20)个苹果，其中第𝑖个重量为$p_i​(1≤p_i​≤10^9)$。现在要将苹果分成两组，使得两组重量和之差最小化。输出其最小值。

输入格式

第一个输入行有一个整数 n ：苹果的数量。 下一行有n个整数$p_1​，p_2​,...,p_n$​ ：每个苹果的重量

输出格式

打印一个整数:两组重量和之差的最小值

样例 #1

样例输入 #1

5
3 2 7 4 1

样例输出 #1

1

提示

【数据范围】

1≤n≤20

$1≤p_i​≤10^9$ 【样例1说明】 第一组放2、3、4（总重9），第二组放1、7（总重8）