시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 768 MB23161473.684%

## 문제

Kim is playing a city-building simulation game in an infinite chessboard. Every cell is denoted with two integer $(x, y)$. Two cells are adjacent if they share an edge - formally, cell $(x, y)$ is adjacent with four cells, $\{(x+1, y), (x, y+1), (x-1, y), (x, y-1)\}$.

In the beginning (day 0), city $i$ occupies the single cell $(x_i, y_i)$. If a cell is occupied by any city, then it’s called  *developed cells*. Thus, in day 0, there is exactly $N$ developed cells.

After each day, the city will grow and expand itself by occupying any undeveloped adjacent cells. Formally, for each city $i$, let $S_i$ be the set that is adjacent to at least one cell in city $i$. Starting from city 1 to city $n$, any undeveloped cell in $S_i$ becomes the part of city $i$, and become developed.

We call two city $u, v$ “connected”, when you can move between $(x_u, y_u)$ to $(x_v, y_v)$ by only passing between adjacent developed cells. For two city $u, v$, let $f(u, v)$ the first day where two city $u, v$ become connected. Kim is interested in each values of $f(u, v)$, but there are too much values to consider. Thus, Kim only want to calculate $\sum_{1 \leq i < j \leq N}{f(u, v)}$ for a given first developed cells.

## 입력

The first line contains the number of city $N$.

In next $N$ lines, the position of $i$-th city’s starting cell is given as two integer $x_i, y_i$.

## 출력

Print $\sum_{1 \leq u < v \leq N}{f(u, v)}$, when $f(u, v)$ is the first day where two city $u, v$ become connected.

## 제한

• $1 \leq N \leq 250000$
• $-10^7 \leq x_i, y_i \leq 10^7$
• All given cells are distinct

## 예제 입력 1

5
-3 2
0 0
0 5
1 2
4 3


## 예제 출력 1

19


## 예제 입력 2

3
0 2
4 0
0 0


## 예제 출력 2

5


In Day 0 :

100000
000000
300020


In Day 1 :

110000
100020
330222


In Day 2 :

111020
110222
332222


$f(1, 2)=2$, $f(1, 3) = 1$, $f(2, 3) = 2$. Thus the answer is $5$