Рабочее место участника

Конечно же, все вы когда-нибудь играли в домино. Как карты и игральные кости, домино является простым способом убивания времени, подходящим для любого возраста. Каждая костяшка домино состоит из двух частей, в которых размещаются от 0 до 6 точек. Рассмотрим следующий ряд из нескольких костяшек домино:

Подсчитав общее количество точек на верхней и нижней частях этих костяшек, мы получим соответственно суммы 14 (`1\ +\ 5\ +\ 3\ +\ 2\ \ +\ 1\ +\ 2`) и 20 (`3\ +\ 4\ +\ 6\ +\ 0\ +\ 4\ +\ 3`).

Заметим, что если убрать некоторые костяшки, мы можем получить равные суммы на верхней и нижней строках. Для костяшек, приведенных выше, если убрать следующие две костяшки, то мы получим обе суммы равными 10 (`1\ +\ 5\ +\ 2\ +\ 2\ =\ 3\ +\ 4\ +\ 0\ +\ 3`):

В данном случае это минимальное число костяшек, которые надо убрать, чтобы получить равные суммы. А как насчет решения этой задачи в общем случае?

Вам даны расположение и ориентация `N` костяшек домино. Ваша задача – найти наименьшее число костяшек `D`, которые необходимо убрать из данного набора, чтобы суммы числа точек верхних и нижних частях ряда из костяшек домино стали равны. Это число `D` может быть равно 0 в случае, если суммы в верхней и нижней строках уже равны, или `N`, когда другого варианта, кроме как удалить все костяшки, получив две нулевые суммы, нет. При этом вы не можете поворачивать костяшки, чтобы поменять верхние и нижние точки местами.

В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 5000`) – количество костяшек домино. Далее следуют ровно `N` строк, в каждой из которых находится пара целых чисел `U_i` и `L_i` (`0\ ≤\ U_i,\ \ L_i\ ≤\ 6`) – количества точек на верхней и нижней частях `i`-й костяшки соответственно.

Вывести единственное целое число `D` – минимальное количество костяшек, которое нужно убрать.

6
1 3
5 4
3 6
2 0
1 4
2 3

2

4
1 5
4 3
2 1
0 6

4

3
4 4
3 6
5 2

0