Oil Pipeline Problem

Problem Description

An oil company plans to build a main east-to-west oil pipeline. The pipeline must pass through an oil field that has $n$ oil wells. From each well, a connecting pipeline must run along the shortest path (either south or north) to join the main pipeline.

Given the positions of the $n$ wells, with their $x$ coordinate (east-west) and $y$ coordinate (north-south), how should the optimal position of the main pipeline be determined, i.e. the position that minimizes the total length of the connecting pipelines from all wells to the main pipeline? Prove that the optimal position can be determined within the required time.

Input Format

The first line is the number of oil wells $n$.

The following $n$ lines give the position of each well, with two integers $x$ and $y$ per line.

Output Format

A single line containing the minimum total length of the connecting pipelines from the wells to the main pipeline.

Sample Input

5
1 2
2 2
1 3
3 -2
3 3

Sample Output

6

Constraints

Data Range and Notes

For all test cases, $1 \le n \le 10000$, $-10^4 \le x, y \le 10^4$.