Description

On a grid-partitioned playground, $n$ soldiers are scattered on grid points, each represented by integer coordinates $(x, y)$.

A soldier can move one step up, down, left, or right along grid edges, but at any moment, at most one soldier may occupy any grid point.

By order, they must form a neat horizontal lineup, that is, the sequence $(x, y), (x+1, y), \ldots, (x+n-1, y)$. Determine how to choose $x$ and $y$ so that the total number of steps taken by all soldiers to line up is minimized.

Input Format

The first line contains an integer $n$ — the number of soldiers.

Lines $2$ to $n+1$ each contain $2$ integers. On line $i+1$, the integers $x_i, y_i$ denote the coordinates of the $i$-th soldier.

Output Format

Output a single integer on one line — the answer.

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

8

Hint

Constraints: For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^4$, $-10^4 \leq x, y \leq 10^4$.

Translated by ChatGPT 5