Pets and Friends#11694
Anton's birthday is coming soon, and he decided to invite his friends over. He has friends. Some of them have a dog, a cat, or both pets. But also some of them are afraid of dogs, cats, or both animals at the same time.
Information about the -th friend (1 \le i \le n) is represented with two integers a_i and b_i varying from to , where a_i corresponds to the pets that a friend has, and b_i corresponds to the animals which they are afraid of. Here are the meanings of these digits:
stands for not having / not being afraid of either;
stands for a dog;
stands for a cat;
stands for both animals.
Let the "x y" person be a person that can be described with digits and . Here are some possible examples of friends:
a "1 2" person has a dog and is afraid of cats;
a "0 1" person does not have a dog or a cat and is afraid of dogs;
a "3 0" person has a dog and a cat and is not afraid of them;
a "0 3" person does not have either of these animals and is afraid of them, and so on.
All Anton's friends love their pets, so they will not come over without them. But he cannot invite a friend who is afraid of some species of animal and a friend who owns a pet of this species at once.
You need to determine the maximum number of friends Anton can invite.
Please note that:
Anton does not have either and is not afraid of either of these pets;
The combination of invited friends may consist of friends who do not own either pets (for all the indices of friends invited, a_j may be equal to );
It is guaranteed that there are no friends who are afraid of their pets.
The first line contains one integer (1 \le n \le 10^5) — the number of Anton's friends.
Each of the next lines contains the information about each friend in the form of two digits a_i,b_i (0 \leq a_i,b_i \leq 3) separated by space, where a_i stands for pets a friend has and b_i — for animals they are afraid of.
It is guaranteed that there are no friends who are afraid of their pets.
In the only line, you need to output the maximum number of guests that Anton can invite so that there are no friends who are afraid of any of the other's pets.
Example
Example 1
Example 2
In the first sample, both friends cannot be invited at once since they both are afraid of each other's pet. But any one of them can still be the only friend invited.
In the second sample, Anton cannot invite all his friends at once since the second one has a cat which the first and the third ones are afraid of. But the first and the third friends can be invited together.
In the third sample, there are the possible combinations of friends invited:
the -st, -rd, and the -th ones;
the -nd, -th, and the -th ones.
It can be shown that Anton cannot invite more than friends in this sample.
( points): none of the friends is afraid of either of the animals;
( points): every friend has exactly one pet and is afraid of exactly one animal;
( points): none of the friends has a cat;
( points): every friend has at most one pet and is afraid of at most one animal;
( points): n \le 20;
( points): no additional constraints.