OI题库

【问题描述】

多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的n个多米诺骨牌如图8-1所示。

编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。上方块中点数之和记为$\sum_1$，下方块中点数之和记为$\sum_2$，它们的差为$|\sum_1-\sum_2|$。例如在图8-1中，$\sum_1$=6+1+1+1=9，$\sum_2$=1+5+3+2=11，$|\sum_1-\sum_2|=2$。每个多米诺骨牌可以旋转180°，使得上下两个方块互换位置。

对于图8-1中的例子，只要将最后一个多米诺骨牌旋转180°，可使上下2行点数之差为0。

【输入】

输入文件的第一行是一个正整数n(1≤n≤1000)，表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数，表示多米诺骨牌上下方块中的点数a和b，且1≤a，b≤6。

【输出】

输出文件仅一行，包含一个整数。表示求得的最小旋转次数。

【样例】

dom.in

4

6 1

1 5

1 3

1 2

dom.out

1