問題文

以下の図のような盤面があります。
縦は $H$ 行であり、$i$ 行目には $i + W - 1$ 個のマスが存在し、$i$ 行目の左から $j$ 個目のマスの座標は $(i, j)$ です。
それぞれのマスは周囲の $6$ 方向のマスと隣接しています。
より厳密には、$(i, j)$ のマスは $(i-1, j-1)$, $(i-1, j)$, $(i, j-1)$, $(i, j+1)$, $(i+1, j)$, $(i+1, j+1)$ の各マスに、マスが存在する限り隣接しています。
この盤上に、$W$ 個のコマが置かれています。コマ $k$ ははじめ$(x_k, y_k)$に置かれています。

あなたは以下の操作を何度でも行うことができます。

コマを一つ選び、隣接するマスにコスト $1$ を払って移動させる。(同じマスに複数のコマが存在してもかまいません。また、盤面の外に移動することはできません。)

全てのコマが $1$ 行目の $W$ 個のマスに一つずつ置かれている状態にするのに必要な、最小のコストを求めてください。

制約

• $1≤H, W≤200$
• $1≤x_i≤H$
• $1≤y_i≤W + x_i - 1$
• $(x_i, y_i)$は互いに異なる
• 入力される値は全て整数

入力

$H\ W$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$        
$x_W\ y_W$

出力

最小のコストを出力せよ。

サンプル