曼哈顿距离之和

题目描述

给定平面上的n个点，其中每个点的位置用坐标(x, y)来表示。定义任意两点(x, y)和(x', y')之间的城市距离为 |x - x'| + |y - y'|。您的任务是计算给定的n个点之间所有可能的点对的城市距离之和。

输入格式

输入的第一行包含一个整数n，表示点的数量。接下来的n行，每行包含两个整数xi和yi，表示第i个点的坐标。

输出格式

输出一个整数，表示所有点对之间的城市距离之和。

样例 #1

样例输入 #1

3
1 2
1 3
2 5

样例输出 #1

8

提示

数据范围 对于30%的数据，满足1 <= n <= 1000。

对于60%的数据，满足1 <= n <= 50000。

对于100%的数据，满足1 <= n <= 300000，-10^6 <= xi, yi <= 10^6