KOI국은 xy 평면으로 표현될 수 있다. KOI 국에는 N개의 집이 있으며 i번째 집(1 ≤ i ≤ N) 의 좌표는 (Xi, Yi)이다.

모든 집의 좌표가 서로 다름이 보장된다. 또한, i번째 집에는 i번째 시민이 산다.

KOI국에 명절이 찾아와 시간 0에, 모든 시민들은 동서남북 중 방향을 하나 골라 그 방향으로 시간당 1의 좌표의 속도로 이동하기 시작한다.

만약 i번째 사람이 동쪽을 고르면, t초 (t ≥ 0)후, 이 사람의 좌표는 (Xi + t, Yi)가 된다.

만약 i번째 사람이 서쪽을 고르면, t초 (t ≥ 0)후, 이 사람의 좌표는 (Xi - t, Yi)가 된다.

만약 i번째 사람이 남쪽을 고르면, t초 (t ≥ 0)후, 이 사람의 좌표는 (Xi, Yi - t)가 된다.

만약 i번째 사람이 북쪽을 고르면, t초 (t ≥ 0)후, 이 사람의 좌표는 (Xi, Yi + t)가 된다.

하지만, 시간 0에 시민 1은 코로나에 걸려 있다. 만약 어떤 시간에 시민 a, b (1 ≤ a ≤ N), (1 ≤ b ≤ N)가 동일한 위치에 있으며

a는 코로나에 걸려 있고 b는 코로나에 걸려 있지 않는다면 b 또한 코로나에 걸리게 된다.

안타깝게도 아직 백신이 개발되지 않아 코로나 바이러스는 치유되지 않는다.

각 사람들이 이동할 방향을 아직 정하지 않은 상태이다. 새로운 정부에서 보건복지부 장관으로 임명된 당신은

최악의 상황에서 10^100의 시간이 흘렀을 때 최대 몇명의 사람들이 감염될 수 있는지 구해야 한다.

1 ≤ N ≤ 100 000.

0 ≤ Xi ≤ 500 000 000 (1 ≤ i ≤ N).

0 ≤ Yi ≤ 500 000 000 (1 ≤ i ≤ N).

(Xi, Yi) ≠ (Xj, Yj) (1 ≤ i < j ≤ N).

Subtask 1 (5점) : N ≤ 7, Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N)

Subtask 2 (8점) : N ≤ 15, Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N)

Subtask 3 (6점) : N ≤ 100, Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N), X1 = 0, Y1 = 0

Subtask 4 (6점) : N ≤ 100, Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N)

Subtask 5 (12점) : N ≤ 3 000

Subtask 6 (32점) : Xi ≠ Xj (1 ≤ i < j ≤ N), Yi ≠ Yj (1 ≤ i < j ≤ N)

Subtask 7 (31점) : 추가 제한 조건 없음

코로나 바이러스 timer 5s memory 512MB

코로나 바이러스 5s 512MB