题目描述

给定 $N$ 份礼物，每份礼物包含两本书，每本书有一个价值。

需要$将这些书分成两组$， 使得两组书的总价值之差尽可能小。

求最小的价值差。

例如，有 $4$ 份礼物，每份礼物中书的价值(两个数)用一对括号括起来表示，如: $(3, 5), (7, 11), (8, 8), (2, 9)$。

可以把 $3, 7, 8, 2$ 分为一组，其余的分为另一组，价值差为:$5+11+8+9−3−7−8−2 = 13$;

也可以把 $3 7 8 9$ 分为一组，其余的分为另一组，价值差为:$3+7+8+9−5−11−8−2 = 1$， 这是最好的方案。

输入格式

第一行:整数 $N(1 ≤ N ≤ 30)$，表示礼物的数量。

接下来 $N$ 行:每行两个整数，表示该礼物中两本书的价值 (价值范围在 $1$ 到 $30$ 之 间)。

输出格式

一个非负整数，表示两组书的最小价值差。

样例 1 输入

4 
3 5 
7 11 
8 8
2 9

样例 1 输出

1

数据范围

对于 $100\%$ 的数据满足:$1 ≤ N ≤ 30$