Description

Original problem at JOISC 2021 Day1 T2 IOI Fever

JOI Kingdom is represented by a xy-plane. There are $N$ houses in JOI Kingdom numbered from $1$ to $N$. The coordinate of the house $i$ $(1 \leq i \leq N)$ is $(X_i, Y_i)$. Different houses have different coordinates. A citizen lives in each house. The citizen in the house $i$ is called the citizen $i$. A long holiday season begins in JOI Kingdom. At time $0$, every citizen leaves the house, and starts traveling.

In the beginning, every citizen chooses one of east, west, south, north, which is the direction for traveling.

The citizens will travel in the following way.

• If the citizen $i$ chooses east, the citizen moves along the $x$-axis toward the positive direction with speed $1$. In other words, at time $t$ $(t \geq 0)$, the coordinates of the citizen $i$ becomes $(X_i + t, Y_i)$.
• If the citizen $i$ chooses west, the citizen moves along the $x$-axis toward the negative direction with speed $1$. In other words, at time $t$ $(t \geq 0)$, the coordinates of the citizen $i$ becomes $(X_i − t, Y_i)$.
• If the citizen $i$ chooses south, the citizen moves along the $y$-axis toward the negative direction with speed $1$. In other words, at time $t$ $(t \geq 0)$, the coordinates of the citizen $i$ becomes $(X_i, Y_i − t)$.
• If the citizen $i$ chooses north, the citizen moves along the $y$-axis toward the positive direction with speed $1$. In other words, at time $t$ $(t \geq 0)$, the coordinates of the citizen $i$ becomes $(X_i, Y_i + t)$.

Unfortunately, at time $0$, the citizen $1$ is infected with IOI fever, which is a newly discovered infectious disease. At time $0$, there are no infected people other than the citizen $1$. The IOI fever is transmitted among citizens in the following way.

• Assume that, at a certain time, the citizen $a$ $(1 \leq a \leq N)$ and the citizen $b$ $(1 \leq b \leq N)$ have the same coordinates, the citizen $a$ is infected with IOI fever, and the citizen b is not infected with IOI fever. Then, the citizen $b$ becomes infected with IOI fever.

The IOI fever is not transmitted by other methods. Moreover, since IOI fever is an incurable disease, infected citizen will not be recovered.

As a minister of JOI Kingdom, you need to estimate how many citizens will be infected with IOI fever if the citizens make the worst possible choice.

Write a program which, given the number of houses and the coordinate of each house, calculates the largest possible number of infected citizens at time $10^100$.

Input Format

In the first line, there is a only integer $N$.

In the following $N$ lines, there are two integers $X_i$ and $Y_i$ in each line.

Output Format

Write one line to the standard output. Output the largest possible number of infected citizens at time $10^100$.

Sample 1

2
0 0
4 3

1

In this sample input, the positions of the houses are as follows.

For example, assume that the citizen $1$ chooses east and the citizen $2$ chooses west.

Then, at any time, the coordinates of citizens $1$ and $2$ are different. Thus the citizen $2$ will not be infected. Therefore the citizen $1$ is the only infected citizen at time $10^100$. The number of infected citizens is $1$.

Regardless of the choices of the directions of the citizens $1$ and $2$, the number of infected citizens cannot be larger than $1$. Hence the largest possible number of infected citizens is $1$, and output $1$.

This sample input satisfies the constraints of subtasks $1, 2, 3, 4, 5, 6, 7$.

3
1 2
2 1
4 3

3

In this sample input, the positions of the houses are as follows.

For example, assume that the citizen $1$ chooses east, the citizen $2$ chooses north, the citizen $3$ chooses west. Then the IOI fever is transmitted among citizens in the following way.

• At time $0$, the citizen $1$ is the only infected citizen.
• At time $1$, the coordinates of the citizens $1, 2, 3$ are $(2, 2), (2, 2), (3, 3)$, respectively. The coordinates of the citizens $1$ and $2$ are the same. At that time, the citizen $1$ is infected with IOI fever, and the citizen $2$ is not infected with IOI fever. Hence the citizen $2$ becomes infected with IOI fever.
• At time $2$, the coordinates of the citizens $1, 2, 3$ are $(3, 2), (2, 3), (2, 3)$, respectively. The coordinates of the citizens $2$ and $3$ are the same. At that time, the citizen $2$ is infected with IOI fever, and the citizen $3$ is not infected with IOI fever. Hence the citizen $3$ becomes infected with IOI fever.

Finally, the number of infected citizens becomes $3$. Since it is the largest possible value, output $3$.

This sample input satisfies the constraints of subtasks $1, 2, 4, 5, 6, 7$.

15
5 6
2 9
12 0
4 11
3 12
6 5
0 8
9 10
11 13
8 7
13 2
1 1
7 14
10 4
14 3

9

Assume that the citizen $1$ chooses north and the citizen $2$ chooses south. Then the IOI fever is transmitted among citizens in the following way.

• At time $0$, the citizen $1$ is the only infected citizen.
• At time $0.5$, both of the coordinates of the citizens $1,~2$ are $(20, 20.5)$.

At that time, the citizen $1$ is infected with IOI fever, and the citizen $2$ is not infected with IOI fever. Hence the citizen $2$ becomes infected with IOI fever. Finally, the number of infected citizens becomes $2$. Since it is the largest possible value, output $2$.

This sample input satisfies the constraints of subtasks $5, 7$.

2
20 20
20 21

2

This sample input satisfies the constraints of subtasks $2, 4, 5, 6, 7$.

30
275810186 246609547
122805872 99671769
243507947 220373844
281305347 252104708
237805644 214671541
172469077 149334974
222589229 229887956
160653451 208404690
241378966 211098219
144302355 224755786
186392385 163258282
199129390 169928751
294937491 265736852
196096122 172962019
314342944 285142305
202720470 166337671
157037485 133903382
263858979 240724876
210720220 181519581
296402036 267201397
186021287 183036854
195081930 173976211
328293029 299092390
261195361 238061258
323595085 294394446
299933764 270733125
240976723 128081418
188501753 165367650
277832422 248631783
119896220 96762117

11

This sample input satisfies the constraints of subtasks $4, 5, 6, 7$.

Constraints

For all test data, it is guaranteed that $1 \le N \le {10}^5,$ $1 \le X_i, Y_i \le 5 \times {10}^8,$ $(X_i, Y_i) \ne (X_j, Y_j)~(1\le i < j\le N)$.

Subtask	Score	Additional Constraints
$1$	$5$	$N \le 7,$ $X_i \ne X_j,$ $Y_i \ne Y_j$
$2$	$8$	$N \le 15,$ $X_i \ne X_j,$ $Y_i \ne Y_j$
$3$	$6$	$N \le 100,$ $X_i \ne X_j,$ $Y_i \ne Y_j,$ $X_1 = 0,$ $Y_1 = 0$
$4$		$N \le 100,$ $X_i \ne X_j,$ $Y_i \ne Y_j$
$5$	$12$	$N \le 3000$
$6$	$32$	$X_i \ne X_j,$ $Y_i \ne Y_j$
$7$	$31$	No additional constraints