Vương quốc JOI được biểu diễn bằng mặt phẳng tọa độ \(xy\). Có \(N\) ngôi nhà, đánh số từ \(1\) đến \(N\). Nhà \(i\) có tọa độ \((X_i,Y_i)\); các nhà ở những vị trí đôi một khác nhau. Mỗi nhà có một người dân sinh sống. Người sống trong nhà \(i\) được gọi là người dân \(i\).

Một kỳ nghỉ dài bắt đầu. Tại thời điểm \(0\), tất cả mọi người rời nhà để đi du lịch. Mỗi người chọn một hướng cố định trong bốn hướng đông, tây, nam, bắc ngay từ đầu, rồi di chuyển như sau:

• Chọn đông: đi theo chiều dương trục \(x\) với vận tốc \(1\). Tại thời điểm \(t \ge 0\), người \(i\) ở \((X_i+t,Y_i)\).
• Chọn tây: đi theo chiều âm trục \(x\) với vận tốc \(1\). Tại thời điểm \(t \ge 0\), người \(i\) ở \((X_i-t,Y_i)\).
• Chọn nam: đi theo chiều âm trục \(y\) với vận tốc \(1\). Tại thời điểm \(t \ge 0\), người \(i\) ở \((X_i,Y_i-t)\).
• Chọn bắc: đi theo chiều dương trục \(y\) với vận tốc \(1\). Tại thời điểm \(t \ge 0\), người \(i\) ở \((X_i,Y_i+t)\).

Không may, tại thời điểm \(0\), người dân \(1\) mắc căn bệnh truyền nhiễm mới được phát hiện mang tên sốt IOI. Ban đầu không có ai khác mắc bệnh. Bệnh lây theo quy tắc sau: nếu tại một thời điểm, hai người \(a,b\) có cùng tọa độ, người \(a\) đã mắc bệnh còn người \(b\) chưa mắc, thì người \(b\) cũng mắc bệnh ngay lúc đó.

Bệnh không lây bằng bất kỳ cách nào khác. Đây là bệnh không thể chữa khỏi, nên người đã mắc bệnh sẽ không hồi phục.

Là một bộ trưởng, bạn cần ước tính tình huống xấu nhất. Cho số nhà và tọa độ từng nhà, hãy tính số người mắc bệnh lớn nhất có thể tại thời điểm \(10^{100}\), xét tất cả các cách chọn hướng của mọi người.

Dữ liệu vào

Đọc từ đầu vào chuẩn, tất cả các giá trị đều là số nguyên:

N
X_1 Y_1
...
X_N Y_N

Dữ liệu ra

In một dòng chứa số người mắc bệnh lớn nhất có thể tại thời điểm \(10^{100}\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(0 \le X_i,Y_i \le 500\,000\,000\) \((1 \le i \le N)\).
• \((X_i,Y_i) \ne (X_j,Y_j)\) \((1 \le i<j \le N)\).

Chấm điểm

Trong bảng dưới, "hoành độ và tung độ đôi một khác nhau" nghĩa là \(X_i\ne X_j\) và \(Y_i\ne Y_j\) với mọi \(1\le i<j\le N\).

1. \(5\) điểm: \(N\le7\); hoành độ và tung độ đôi một khác nhau.
2. \(8\) điểm: \(N\le15\); hoành độ và tung độ đôi một khác nhau.
3. \(6\) điểm: \(N\le100\); hoành độ và tung độ đôi một khác nhau; \(X_1=Y_1=0\).
4. \(6\) điểm: \(N\le100\); hoành độ và tung độ đôi một khác nhau.
5. \(12\) điểm: \(N\le3\,000\).
6. \(32\) điểm: Hoành độ và tung độ đôi một khác nhau.
7. \(31\) điểm: Không có giới hạn bổ sung.

Ví dụ

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

Nguồn

JOI 2021 Spring Training Camp, Contest 1, JCIOI. Bản dịch tiếng Việt và hình trích từ đề chính thức theo CC BY-SA 4.0.