You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

曼哈顿距离之和

题目描述

给定平面上的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