Домашние животные и друзья

Скоро у Антона день рождения, и он решил пригласить своих друзей. У него $n$ друзей. У некоторых из них есть собака, кошка или оба питомца. Но также у некоторых из них боятся собак, кошек или обоих одновременно.

Информация о $i$-м друге $(1\le i\le n)$ представлена двумя целыми числами $a_i$ и $b_i$, варьирующимися от $0$ до $3$, где $a_i$ соответствует питомцам, которые есть у друга, а $b_i$ соответствует животным, которых они боятся. Вот значения этих цифр:

• $0$ означает отсутствие / отсутствие страха перед любым из них;

• $1$ означает собаку;

• $2$ означает кошку;

• $3$ означает обоих животных.

Пусть человек «x y» будет человеком, который может быть описан цифрами $x$ и $y$. Вот некоторые возможные примеры друзей:

• человек «1 2» имеет собаку и боится кошек;

• человек «0 1» не имеет собаки или кошки и боится собак;

• человек «3 0» имеет собаку и кошку и не боится их;

• человек «0 3» не имеет ни одного из этих животных и боится их, и так далее.

Все друзья Антона любят своих питомцев, поэтому они не придут без них. Но он не может пригласить друга, который боится какого-то вида животного, и друга, который владеет питомцем этого вида одновременно.

Вам нужно определить максимальное количество друзей, которых Антон может пригласить.

Обратите внимание, что:

• Антон не боится и не имеет ни одного из этих питомцев;

• Комбинация приглашенных друзей может состоять из друзей, у которых нет ни одного питомца (для всех индексов $j$ приглашенных друзей $a_j$ может быть равно $0$);

• Гарантируется, что нет друзей, которые боятся своих питомцев.

Входные данные

Первая строка содержит одно целое число $n$ $(1\le n\le 10^5)$ — количество друзей Антона.

Каждая из следующих $n$ строк содержит информацию о каждом друге в виде двух цифр $a_i,b_i$ $(0\le a_i,b_i\le 3)$, разделенных пробелом, где $a_i$ означает питомцев друга, а $b_i$ — животных, от которых они боятся.

Гарантируется, что нет друзей, которые боятся своих питомцев.

Выходные данные

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

Примеры

Примечание

В первом примере оба друзья не могут быть приглашены одновременно, так как они оба боятся питомцев друг друга. Но любой из них все равно может быть единственным приглашенным другом.

Во втором примере Антон не может пригласить всех своих друзей одновременно, так как у второго друга есть кошка, от которой боятся первый и третий. Но первого и третьего друга можно пригласить вместе.

В третьем примере есть $2$ возможные комбинации приглашенных друзей:

• $1$-й, $3$-й и $7$-й;

• $2$-й, $4$-й и $7$-й.

Можно показать, что Антон не может пригласить больше $3$ друзей в этом примере.

Оценивание

1. ($9$ баллов): ни один из друзей не боится ни одного из животных;

2. ($14$ баллов): у каждого друга ровно один питомец и они боятся ровно одного животного;

3. ($17$ баллов): ни у одного друга нет кошки;

4. ($29$ баллов): у каждого друга максимум один питомец и они боятся максимум одного животного;

5. ($8$ баллов): $n\le 20$;

6. ($23$ балла): нет дополнительных ограничений.