题面描述

在一个坐标平面上，有 $N$ 个点 $P_1, P_2, \ldots, P_N$，其中点 $P_i$ 的坐标为 $(X_i, Y_i)$。两点 $A$ 和 $B$ 之间的距离 $\text{dist}(A, B)$ 定义如下：

遥远的她最初位于点 $A$。遥远的她在位置 $(x, y)$ 可以跳到 $(x+1, y+1)$, $(x+1, y-1)$, $(x-1, y+1)$ 或 $(x-1, y-1)$ 中的一个点，完成一次跳跃。

$\text{dist}(A, B)$ 定义为从点 $A$ 到点 $B$ 需要的最小跳跃次数。如果在任意次数的跳跃后无法从点 $A$ 到达点 $B$，则令 $\text{dist}(A, B) = 0$。

计算以下和：

$$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \text{dist}(P_i, P_j) $$

输入格式

一行一个整数 $N$ ，代表点的数量。

接下来 $N$ 行，每行两个整数 $(X_i, Y_i)$

输出格式

一行一个整数，表示答案

3
0 0
1 3
5 6

3

5
0 5
1 7
2 9
3 8
4 6

11

数据范围与约定

• 对于 $30\%$ 的数据，满足 $N \leq 100$
• 对于 $100\%$ 的数据，满足 $2 \leq N \leq 2 \times 10^5, 0 \leq X_i, Y_i \leq 10^8$ 保证没有相同的 $(X_i, Y_i)$