Description

In the JOI Kingdom, there are $N$ palaces. The $i$-th palace is located at $(X_i, Y_i)$. Each palace is home to one prince; the prince in the $i$-th palace is Prince $i$. Starting from time $0$, every prince will leave their own palace and start moving. They can choose one of the four directions: east, south, west, or north.

• If they choose east, then after time $t$, their position changes from $(x, y)$ to $(x + t, y)$.
• If they choose west, then after time $t$, their position changes from $(x, y)$ to $(x - t, y)$.
• If they choose south, then after time $t$, their position changes from $(x, y)$ to $(x, y - t)$.
• If they choose north, then after time $t$, their position changes from $(x, y)$ to $(x, y + t)$.

$t$ does not have to be an integer.

The directions will not be given; you can plan them yourself.

Unfortunately, Prince $1$ has been infected with the IOVID-114514 virus, and at time $0$, only Prince $1$ is infected.

The IOVID-114514 virus spreads in the following way:

• If at some time, Prince $a$ and Prince $b$ are at the same coordinate, and Prince $a$ is infected while Prince $b$ is not, then Prince $a$ will infect Prince $b$.

The IOVID-114514 virus has no other way of spreading, and the poor King JOI 114514 has not found any cure.

(Disinfectant cannot cure it either.)

King JOI 114514 wants you to find the maximum number of princes that can be infected by time $10^{100}$.

Input Format

The first line contains an integer $N$, representing the number of palaces.

The next $N$ lines each contain two integers $X_i, Y_i$, representing the coordinates of a palace.

Output Format

Output one integer on a single line, representing the answer.

2
0 0
4 3

1

3
1 2
2 1
4 3

3

2
20 20
20 21

2

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

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

Hint

Explanation of Sample 1

We plan Prince $1$ to move east, and Prince $2$ to move west.

It is not hard to see that no matter how they move, Prince $1$ can never meet Prince $2$, so only Prince $1$ is infected.

Explanation of Sample 2

We plan Prince $1$ to move east, Prince $2$ to move north, and Prince $3$ to move west.

• At time $0$, Prince $1$ is infected.
• At time $1$, Prince $1$ and Prince $2$ are at the same coordinate, so Prince $2$ becomes infected.
• At time $2$, Prince $2$ and Prince $3$ are at the same coordinate, so Prince $3$ becomes infected.

Explanation of Sample 3

We plan Prince $1$ to move north, and Prince $2$ to move south.

• At time $0$, Prince $1$ is infected.
• At time $0.5$, Prince $1$ and Prince $2$ are at the same coordinate, so Prince $2$ becomes infected.

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (5 pts): $N \le 7$, satisfies Property A.
• Subtask 2 (8 pts): $N \le 15$, satisfies Property A.
• Subtask 3 (6 pts): $N \le 100$, satisfies Properties A and B.
• Subtask 4 (6 pts): $N \le 100$, satisfies Property A.
• Subtask 5 (12 pts): $N \le 3000$.
• Subtask 6 (32 pts): satisfies Property A.
• Subtask 7 (31 pts): no special restrictions.

For $100\%$ of the testdata: $1 \le N \le 10^5$, $0 \le X_i, Y_i \le 5 \times 10^8$, and all palace coordinates are distinct.

The properties are:

• Property A: $X_i \ne X_j$, $Y_i \ne Y_j$.
• Property B: the coordinate of Palace $1$ is the origin.

Notes

Translated from The 20th Japanese Olympiad in Informatics Spring Training Camp, Day1 B IOI 熱の感染拡大 (IOI Fever) English version.

Translated by ChatGPT 5