コイン集め(Coin Collecting)

JOI 氏のコレクションルームには非常に大きな机があり，その上には何枚もの貴重なコインがある．机の掃除をするために，JOI 氏はコインを整理して並べることにした．

机は2 000 000 001 $\times$ 2 000 000 001 のマス目になっている．列には左から順に-1 000 000 000 から1 000 000 000までの番号がつけられており，行には下から順に-1 000 000 000 から1 000 000 000 までの番号がつけられている．列の番号が$x$，行の番号が$y$ であるマスを($x, y$) で表すことにする．

コインは$2N$ 枚あり，現在，$i$ 番目($1 \leq i \leq 2N$) のコインはマス($X_i, Y_i$) に置かれている．JOI 氏の目標は，$1 \leq x \leq N$ かつ$1 \leq y \leq 2$ を満たす($x, y$) で表される$2N$ 個のマスに，それぞれコインが1 枚ずつ置かれている状態にすることである．コインを傷つけないようにするため，「コインを1 枚選び，それが置かれているマスと辺で隣り合ったマスのいずれかに，そのコインを移動させる」という操作のみができる．途中，複数のコインが同じマスに置かれていてもよい．JOI 氏は，できるだけ少ない回数の操作で目標を達成したい．

コインの枚数と，現在コインが置かれているマスが与えられたとき，目標を達成するために必要な操作回数の最小値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

$N$
$X_1$ $Y_1$
:
$X_{2N}$ $Y_{2N}$

出力

標準出力に，目標を達成するために必要な操作回数の最小値を1 行で出力せよ．

制約

• $ 1 \leq N \leq 100 000$．
• $ -1 000 000 000 \leq X_i \leq 1 000 000 000 (1 \leq i \leq 2N)$．
• $ -1 000 000 000 \leq Y_i \leq 1 000 000 000 (1 \leq i \leq 2N)$．

入出力例

入力例1

3
0 0
0 4
4 0
2 1
2 5
-1 1

出力例1

15

この入力例では，6 個のコインが下図のように置かれている．太枠で示した位置にコインを集めるのが目標である．

例えば，コインを以下のように移動させると，15 回の操作で目標を達成できる：

• 1 番目のコイン：(0, 0) → (1, 0) → (1, 1) → (1, 2)
• 2 番目のコイン：(0, 4) → (1, 4) → (1, 3) → (2, 3) → (3, 3) → (3, 2)
• 3 番目のコイン：(4, 0) → (4, 1) → (3, 1)
• 5 番目のコイン：(2, 5) → (2, 4) → (2, 3) → (2, 2)
• 6 番目のコイン：(-1, 1) → (0, 1) → (1, 1)

14 回以下の操作で目標を達成することはできないので，15 を出力する．

入力例2

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1

出力例2

9

同じマスに複数のコインが置かれているかもしれない．

入力例3

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

出力例3

8000000029

情報オリンピック日本委員会作 『第18 回日本情報オリンピック(JOI 2018/2019) 本選』

---