|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
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