Distance

Interview

Time limit3sMemory limit1024 MB

Summary

Given N points on a grid, compute the sum of Manhattan distances over all distinct pairs.

Level: Medium5 of 10
Topics: Math, Sorting, Prefix sum, Array
Solved: No attempts yet

Problem

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 spread them 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 trucks 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.

Examples1

Example 1
Input
```
3
1 1
4 5
2 3
```
Expected output
```
14
```