Problem1378--士兵排阵Ⅱ

1378: 士兵排阵Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 162  Solved: 40
[Submit] [Status] [Web Board] [Creator:]

Description

在一个n*n的棋盘上,n个士兵散乱地站在网格上,网格由整数坐标(x,y)表示。士兵们可以在棋盘的网格上、下、左、右移动一步,但在同一时刻任一网格上只能有一名士兵。按照军官的命令,士兵们要整齐地排成一行或者一列。
请计算使所有士兵排成一行或者一列需要的最少移动步数。

Input

第一行一个正整数n,n<=5*10^5。
接下来n行,每行两个正整数x,y,表示该士兵在棋盘内的位置,其中x,y<=n。

Output

输出使所有士兵排成一行或者一列需要的最少移动步数。

Sample Input

5
1 2
2 4
3 4
5 1
5 3

Sample Output

6

Source/Category