Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ 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.
Are you sure you want to participate in this contest ?
If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.
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.