Minimize Domino Rows Difference

There are dominoes arranged in a single row. Each domino consists of two squares (an upper square and a lower square) with dots from 1 to 6. Let \(S_1\) be the sum of dots on the upper squares, and \(S_2\) be the sum of dots on the lower squares. The absolute difference is \(|S_1 - S_2|\). Each domino can be rotated by \(180^\circ\), swapping its upper and lower squares. Your task is to determine the minimum number of rotations required so that the absolute difference between the sums of the two rows, \(|S_1-S_2|\), is minimized.

For example, consider the following dominoes (shown as pairs \((upper, lower)\)):

• (6, 1)
• (1, 5)
• (1, 3)
• (1, 2)

Initially, \(S_1=6+1+1+1=9\) and \(S_2=1+5+3+2=11\), so the absolute difference is \(2\). By rotating the last domino, the configuration becomes:

• (6, 1)
• (1, 5)
• (1, 3)
• (2, 1)

Now, \(S_1=6+1+1+2=10\) and \(S_2=1+5+3+1=10\) with an absolute difference of \(0\), which is optimal with just one rotation.

Note: If no rotations are performed, the initial difference is \(D=\sum_{i=1}^{n}(top_i-bottom_i)\). Rotating a domino that has a pair \((top, bottom)\) changes the contribution of that domino by \(-2\times(top - bottom)\). The goal is to choose a subset of dominoes to rotate in order to minimize \(|D - 2\times(\text{sum of }(top-bottom) \text{ for rotated dominoes})|\) with as few rotations as possible.

inputFormat

The first line contains a positive integer \(n\) (number of dominoes).
Each of the next \(n\) lines contains two space-separated integers representing the number of dots on the upper and lower squares of each domino.

For example:

4
6 1
1 5
1 3
1 2

outputFormat

Output a single integer: the minimum number of rotations required to achieve the minimum possible absolute difference between the sums of the top and bottom dots.

sample

4
6 1
1 5
1 3
1 2

1