Kings

Time limit1sMemory limit512 MB

Summary

Given n kings on an n by n board, find the minimum total moves to shift every king onto the main diagonal, where a move shifts one king one cell horizontally or vertically.

Level: Medium6 of 10
Topics: Two pointers, Greedy, Sorting, Implementation
Solved: No attempts yet

Problem

A hot game of "chess-tidying" begins with a messy board holding several king pieces scattered over the cells. The player must line all the pieces up along the board's primary diagonal, which runs along the black squares.

In one move, unlike in ordinary chess, one king moves one cell horizontally or vertically (not both) to another unoccupied cell.

Given an instance of the game, find the minimum number of moves needed to finish it.

Figure K.1: Illustration of Sample Input 2. In this case, the minimum number of moves needed to place all the kings along the black diagonal is 28, as pictured.

Input

One line with the number of rows and columns, n (1 ≤ n ≤ 500).
Each of the following n lines contains the two-dimensional integer coordinates c and r (1 ≤ c, r ≤ n), the position of one of the kings.

Each king starts at a distinct position.

Output

Print the minimum number of moves needed for the kings to cover the main diagonal (r = c).

Examples2

Example 1
Input
```
3
1 1
2 3
3 2
```
Expected output
```
2
```
Example 2
Input
```
8
6 4
6 8
5 5
5 4
4 8
5 7
7 4
3 7
```
Expected output
```
28
```