题目描述

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

输入格式

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

输出格式

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

5
3 2 7 4 1

1

数据范围与提示

【数据范围】

• 1≤n≤20
• $1≤p_i≤10^9$

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