2020 Rocky Mountain Regional Contest

Start

2021-03-06 10:00 AKST

2020 Rocky Mountain Regional Contest

End

2021-03-06 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -149 days 22:33:01

Time elapsed

5:00:00

Time remaining

0:00:00

Problem G
Distance

The City of Manhattan is organized as a grid of streets and avenues, with streets running in the North-South direction and avenues running in the East-West direction. Streets are numbered from East to West starting from 1, and avenues are numbered from North to South starting from 1. Each intersection is labelled by the street and avenue number $(s, a)$. The distance between two intersections $(s_1, a_1)$ and $(s_2, a_2)$ is $|s_1-s_2| + |a_1-a_2|$.

Your company operates several food trucks at different intersections in Manhattan and you want to have them spread out so they do not compete with each other. To estimate how spread out they are, you have decided to compute the total distance between every distinct pair of your food trucks. A small total distance would mean that on average, a pair of food truck is too close together.

What is the total distance between every distinct pair of food trucks?

Input

The first line of input contains an integer $N$ ($2 \leq N \leq 200\, 000$), which is the number of food trucks.

The next $n$ lines describe the food trucks’ locations. Each of these lines contains two integers $s$ ($1 \leq s \leq 1\, 000\, 000$), which is the street number of this food truck, and $a$ ($1 \leq a \leq 1\, 000\, 000$), which is the avenue number of this food truck.

Output

Display the total distance between every distinct pair of food trucks.

Sample Input 1 Sample Output 1
3
1 1
4 5
2 3
14