Домашні тварини та друзі

Скоро День народження Антона, і він вирішив запросити своїх друзів. У нього є $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$ бали): немає додаткових обмежень.