有一对双胞胎（哥哥和妹妹），关系特别好，什么事都相互谦让。唯独每年到他们生日的那天，他们就会或多或少的有一些不愉快，渐渐的，成了他们的烦恼。

事情是这样的。每年到他们过生日的时候，亲朋好友都会给他们送来礼物，表示祝贺。有的人给他们买同样的礼物，有的人买不一样的礼物。每件礼物都有相应的价值。每个送礼物的人都没有明确说哪个礼物给谁，作为两个双胞胎，他们都希望自己收到的礼物价值高些。这不，今年生日所有的朋友送的礼物都是2本书。为了减少矛盾，双胞胎的妈妈让你来帮忙分配，要求使得两人所获得书本的价值和之间的差距尽可能的小。

例如，有$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 \leq N \leq 30)$,表示礼物的数量，接下来$N$行，每行两个整数，表示每份礼物两本书的价值(价值范围在$1$到$30$之间)。

输出格式

输出一个非负整数，表示最小的价值差。

样例

样例输入

4
3 5
7 11
8 8
2 9

样例输出

1

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$262144\mathrm{KB}$