多米诺骨牌问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有一种多米诺骨牌是平面的,其正面被分成上下两个部分,每一部分的表面或者为空,或者被标上1至6个点。现在有一行多米诺骨牌排列在桌面上,如图1所示: 


顶行(上行)骨牌的点数之和为6+1+1+1=9;底行(下行)骨牌的点数之和为1+5+3+2=11。顶行和底行的差值是2,这个差值是上下两行点数之和的差的绝对值。每个多米诺骨牌都可以上下翻转倒置交换,即上部变为下部,下部变为上部。

现在的任务是,以最少的翻转次数,使得顶行和底行之间的差值最小。对于上面这个例子,我们只需要翻转最后一个骨牌,就可以使得顶行和底行的差值为0。所以这个例子的答案为1。

Input

输入的第1行是一个整数n(1<=n<=1000),表示有n个多米诺骨牌在桌面上排成一行。接下来总共有n行,每行包含两个整数a,b(0<=a,b<=6,中间用空格分开)。第i+1行的a,b分别表示第i个多米诺骨牌的上部和下部的点数(0表示空)。

Output

输出只有一个整数。这个整数表示翻动骨牌的最少次数,从而使得顶行和底行的差值最小。

Sample Input

4
6 1
1 5
1 3
1 2

Sample Output

1

Hint

Source