P1889 Soldiers Line Up

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.

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 a single integer on one line — the answer.

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