도시 확장

Kim은 무한 체스판에서 도시 건설 시뮬레이션 게임을 하고 있다. 각 칸은 두 정수 $(x, y)$로 나타낸다. 두 칸이 인접하다는 것은 변을 공유한다는 뜻이다. 즉, 칸 $(x, y)$는 $\{(x+1, y), (x, y+1), (x-1, y), (x, y-1)\}$의 네 칸과 인접하다.

처음(0일차)에 도시 $i$는 단일 칸 $(x_i, y_i)$를 차지한다. 어떤 도시든 차지한 칸을 개발된 칸이라고 한다. 따라서 0일차에는 개발된 칸이 정확히 $N$개 있다.

매일이 지나면 도시는 인접한 미개발 칸을 차지하며 성장하고 확장한다. 구체적으로, 각 도시 $i$에 대해 $S_i$를 도시 $i$의 적어도 한 칸과 인접한 칸의 집합이라고 하자. 도시 1부터 도시 $n$까지 순서대로, $S_i$에 속한 미개발 칸은 도시 $i$의 일부가 되고 개발된다.

두 도시 $u, v$가 "연결되었다"는 것은 $(x_u, y_u)$에서 $(x_v, y_v)$로 인접한 개발된 칸만 지나서 이동할 수 있다는 뜻이다. 두 도시 $u, v$에 대해 $f(u, v)$를 두 도시 $u, v$가 연결되게 되는 첫 번째 날이라고 하자. Kim은 각 $f(u, v)$의 값에 관심이 있지만 고려해야 할 값이 너무 많다. 따라서 Kim은 주어진 초기 개발 칸에 대해 $\sum_{1 \leq i < j \leq N}{f(u, v)}$만 계산하려고 한다.

첫 번째 줄에는 도시의 수 $N$이 주어진다.

다음 $N$개의 줄에는 $i$번째 도시의 시작 칸 위치가 두 정수 $x_i, y_i$로 주어진다.

$f(u, v)$가 두 도시 $u, v$가 연결되게 되는 첫 번째 날일 때, $\sum_{1 \leq u < v \leq N}{f(u, v)}$를 출력한다.

• $1 \leq N \leq 250000$
• $-10^7 \leq x_i, y_i \leq 10^7$
• 주어지는 모든 칸은 서로 다르다