Description
TAs want to schedule a physical meeting but are too lazy to think about where they want to meet. Since they are lazy and don't want to move too much, please help them find out the optimal meeting location that minimizes the total distance they need to travel.
The distance is calculated using Manhattan Distance, following is how the distance is calculated:
$$\begin{aligned} &p_1 = (x_1, y_1) \\ &p_2 = (x_2, y_2) \\ &\text{distance}(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2| \end{aligned}$$
- Hint 1: It is somehow related to quick sort
- Hint 2: Is it possible to not sort the entire array
Input
The first line contains one integer $N$, representing the number of TA.
The next $N$ lines each contains two integers, $x_i$ and $y_i$, representing the $x$ and $y$ coordinate of each TA respectively.
Contraints
- $1 \leq N \leq 3 \times 10^6$
- $-10^9 \leq x_i , y_i \leq 10^9$
Subtask
- (Testcases 1-4) $1 \leq N \leq 3000$
- (Testcases 5-8) No additional constraints.
Output
Output the minimum total distance they need to travel.
Noted that you should output one single line.