Description

An oil company plans to build a main pipeline running from east to west.

The pipeline must pass through an oil field that has $n$ wells. From each well, a feeder pipeline must connect to the main pipeline along the shortest path (either north or south).

Given the positions of the $n$ wells, with their $x$ coordinates (east–west) and $y$ coordinates (north–south), determine the optimal position of the main pipeline so that the total length of the feeder pipelines from the wells to the main pipeline is minimized. Prove that the optimal position of the main pipeline can be determined within the time limit.

Input Format

The first line contains the number of wells $n$.

Each of the next $n$ lines contains the position of a well: two integers $x$ and $y$.

Output Format

Output a single line with the minimum total length of the feeder pipelines from the wells to the main pipeline.

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

6

Hint

Constraints

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

Translated by ChatGPT 5