Problem E: Light

Problem

$W \times H$ の二次元のマス上に$N$個の街灯がある。
がっちょ君は$(1,1)$からスタートして$(W,H)$に行きたい。
がっちょ君は暗いところが怖いので、街灯により明るくなっているマスしか歩きたくない。
最初、すべての街灯はその街灯のあるマスのみを明るくしている。
そこで、がっちょ君は好きな街灯$i$に対してコスト$r_i$を設定することにした。なお、コストを設定しない街灯があってもよい。
街灯$i$はコスト$r_i$を消費することにより、その街灯を中心にマンハッタン距離で$r_i$以内の範囲を明るくすることができる。ただしコストは正の整数とする。
がっちょ君は上下左右のいずれかの方向に隣接するマスに移動する事ができる。
がっちょ君は$r_i$の合計値を最小になるように設定することにした。そのときの合計値を求めよ。

2つの地点 $(a,b)$ と $(c,d)$ 間のマンハッタン距離は $|a−c|$+$|b−d|$ で表される。

Input

入力は以下の形式で与えられる。

$W$ $H$ $N$
$x_1$ $y_1$
...
$x_N$ $y_N$

入力はすべて整数で与えられる。
1行目に$W$と$H$と$N$が空白区切りで与えられる。
続く$N$行に街灯$i$の座標$($$x_i$,$y_i$$)$が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• $1 \leq W \leq 500$
• $1 \leq H \leq 500$
• $1 \leq N \leq 100$
• $1 \leq N \leq W \times H$
• $1 \leq $$x_i$$ \leq W$
• $1 \leq $$y_i$$ \leq H$
• 同じ座標に複数の街灯はない

Output

$r_i$の合計値の最小値を1行に出力せよ。

Sample Input 1

10 10 1
6 6

Sample Output 1

10

Sample Input 2

5 10 3
3 9
2 8
5 1

Sample Output 2

8

Sample Input 3

1 1 1
1 1

Sample Output 3

0

Note

Link

 

---