C - Find the Point

Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)

Consider an infinite 2-dimensional grid with some marked cells. We are interested in finding the minimum sum of Manhattan distances from all marked cells to some not marked cell .

We define Manhattan distance between two cells with coordinates $a_1, b_1$ and $a_2, b_2$ as $|a_1 - a_2| + |b_1 - b_2|$.


Input

The first line of input contains a single integer $n (1 \leq n \leq 100000)$, the number of marked cells in the grid.
Next $n$ lines contains the coordinates $a_i$ and $b_i$ of marked cells in the grid $(-2^{30} \leq a_i,b_i \leq 2^{30})$.

Output

You should output a single line with the minimum sum of Manhattan distances.

Sample test(s)

Input
4 1 -3 0 1 -2 1 1 -1
Output
10
Input
5 2 2 0 2 4 2 2 0 4 0
Output
11
Input
9 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
Output
24