Hamako Online Judge

TLE
1sec

MLE
256MB

得点
100

問題

JOI氏のコレクションルームには非常に大きな机があり，その上には何枚もの貴重なコインがある．机の掃除をするために，JOI氏はコインを整理して並べることにした．
机は $2000000001$ × $2000000001$ のマス目になっている．列には左から順に $-1000000000$ から $1000000000$ までの番号がつけられており，行には下から順に $-1000000000$ から $1000000000$ までの番号がつけられている．列の番号が $x$，行の番号が $y$ であるマスを($x$, $y$)で表すことにする．
コインは $2N$ 枚あり，現在，$i$ 番目($1$ ≦ $i$ ≦ $2N$)のコインはマス($X$_$i$, $Y$_$i$)に置かれている．JOI氏の目標は，$1$ ≦ $x$ ≦ $N$ かつ $1$ ≦ $y$ ≦ $2$ を満たす($x$, $y$)で表される $2N$ 個のマスに，それぞれコインが $1$ 枚ずつ置かれている状態にすることである．コインを木津付けないようにするため，「コインを $1$ 枚選び，それが置かれているマスと辺で隣り合ったマスのいずれかに，そのコインを移動させる」という操作のみができる．途中，複数のコインが同じマスに置かれていてもよい．JOI氏は，できるだけ少ない回数の操作で目標を達成したい．
コインの枚数と，現在コインが置かれているマスが与えられたとき，目標を達成するために必要な操作回数の最小値を求めるプログラムを作成せよ．

入力

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

$N$
$X$_$1$ $Y$_$1$
:
$X$_$2N$ $Y$_$2N$

出力

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

制約

$1$ ≦ $N$ ≦ $100000$.
$-1000000000$ ≦ $X$_$i$ ≦ $1000000000$($1$ ≦ $i$ ≦ $2N$).
$-1000000000$ ≦ $Y$_$i$ ≦ $1000000000$($1$ ≦ $i$ ≦ $2N$).

小課題

(8 点) $N$ ≦ $10$.
(29 点) $N$ ≦ $1000$.
(63 点) 追加の制約はない.

入出力例

入力例 1

出力例 1

この入力例では，$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

出力例 2

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

入力例 3

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

出力例 3

8000000029

1069 - コイン集め (Coin Collecting)

問題

入力

出力

制約