Minimum Movement Formation

You are given n soldiers positioned on a grid at integer coordinates \((x, y)\). Each soldier can move one step in one of the four cardinal directions (up, down, left, right) along the grid edges. At any given moment, no two soldiers can share the same grid point.

Upon receiving orders, the soldiers must form a horizontal line in consecutive grid positions, specifically at coordinates \((x, y),\ (x+1, y),\ldots,\ (x+n-1, y)\). Your task is to determine the optimal \(x\) and \(y\) (i.e. the starting point of the line) so that the total number of moves required to reposition all soldiers is minimized.

Hint: The optimal \(y\) coordinate is the median of the soldiers' \(y\) coordinates, while the optimal horizontal movement can be computed by sorting the soldiers by their \(x\) coordinates and then shifting them to consecutive positions. In particular, if the sorted \(x\) coordinates are \(x_0, x_1, \ldots, x_{n-1}\), consider the sequence \(a_i = x_i - i\) for \(0 \leq i < n\). The optimal starting \(x\) is the median of the \(a_i\) values. The minimum total moves is the sum of the absolute differences of each soldier's \(y\) coordinate from the median, plus the sum of the absolute differences of the \(x_i\) from \(\text{median}(a_i)+i\).

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input consists of multiple lines. The first line contains a single integer (n) (the number of soldiers). Each of the following (n) lines contains two integers (x) and (y), representing the coordinates of a soldier.

outputFormat

Output a single integer representing the minimum total number of moves required for the soldiers to form a horizontal line with consecutive grid positions.

sample

3
1 1
2 2
3 3

2