题目背景

本题数据保留一部分，请在 此处 获取完整数据。

题目描述

JOI 王国有 $N$ 个宫殿，第 $i$ 个宫殿坐标为 $(X_i,Y_i)$，每个宫殿居住着一个王子，第 $i$ 个宫殿里的王子为 $i$ 号王子。从第 $0$ 时刻开始，每个王子将会从自己的宫殿出发开始走动，他们可以选择东南西北：

• 如果选择东，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x+t,y)$。
• 如果选择西，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x-t,y)$。
• 如果选择南，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x,y-t)$。
• 如果选择北，则 $t$ 时刻过后坐标位置从 $(x,y)$ 变为 $(x,y+t)$。

$t$ 不一定是整数。

方向不会给定，你可以自己规划。

不幸的是，$1$ 号王子染上了 IOVID-114514 病毒，在 $0$ 时刻只有 $1$ 号王子感染了该病毒。

IOVID-114514 病毒按照如下方式进行传播：

• 如果某一个时刻 $a$ 号王子和 $b$ 号王子在同一个坐标上，且 $a$ 号王子感染了病毒，$b$ 号王子没有感染病毒，则 $a$ 号王子会将病毒传染给 $b$ 号王子。

IOVID-114514 病毒没有其他传染方式，可怜的国王 JOI 114514 世也没有发现治愈方法。

（消毒水也不能治愈！）

JOI 114514 世想问问你求第 $10^{100}$ 个时刻的时候最多会有多少个王子感染 IOVID-114514 病毒。

输入格式

第一行一个整数 $N$ 代表宫殿个数。

接下来 $N$ 行每行两个整数 $X_i,Y_i$ 代表一个宫殿的坐标。

输出格式

一行一个整数代表答案。

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

提示

样例 1 解释

我们规划 $1$ 号王子向东，$2$ 号王子向西。

不难发现，不论怎么移动 $1$ 都无法与 $2$ 相遇，只有 $1$ 号王子一个感染者。

样例 2 解释

我们规划 $1$ 号王子向东，$2$ 号王子向北，$3$ 号王子向西。

• 时刻 $0$，$1$ 号王子是感染者。
• 时刻 $1$，$1$ 号王子与 $2$ 号王子坐标重合，$2$ 号王子感染。
• 时刻 $2$，$2$ 号王子与 $3$ 号王子坐标重合，$3$ 号王子感染。

样例 3 解释

我们规划 $1$ 号王子向北，$2$ 号王子向南。

• 时刻 $0$，$1$ 号王子是感染者。
• 时刻 $0.5$，$1$ 号王子和 $2$ 号王子坐标重合，$2$ 号王子感染。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$N \le 7$，满足性质 A。
• Subtask 2（8 pts）：$N \le 15$，满足性质 A。
• Subtask 3（6 pts）：$N \le 100$，满足性质 A 和 B。
• Subtask 4（6 pts）：$N \le 100$，满足性质 A。
• Subtask 5（12 pts）：$N \le 3000$。
• Subtask 6（32 pts）：满足性质 A。
• Subtask 7（31 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le X_i,Y_i \le 5 \times 10^8$，宫殿坐标互不重合。

其中性质分别为：

• 性质 A：$X_i \ne X_j$，$Y_i \ne Y_j$。
• 性质 B：$1$ 号宫殿坐标为原点。

说明

翻译自 第２０回日本情報オリンピック　春季トレーニング合宿 Day1 B IOI 熱の感染拡大 (IOI Fever) 的英文版本。