21785번 - 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 ≤ i ≤ 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 ≥ 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 ≥ 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 ≥ 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 ≥ 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 ≤ a ≤ N) and the citizen b (1 ≤ b ≤ 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¹⁰⁰.

Read the following data from the standard input. Given values are all integers.

N
X1 Y1
.
.
.
XN YN

Write one line to the standard output. Output the largest possible number of infected citizens at time 10¹⁰⁰.

• 1 ≤ N ≤ 100 000.
• 0 ≤ X_i ≤ 500 000 000 (1 ≤ i ≤ N).
• 0 ≤ Y_i ≤ 500 000 000 (1 ≤ i ≤ N).
• (X_i, Y_i) ≠ (X_j, Y_j) (1 ≤ i < j ≤ N).