008 - ダンジョン

問題

Ｂ君は人気のゲーム「ダンジョン」で遊んでいる。
ゲームは、W×H 個のマス目状に区切られた長方形の盤面上で行われる。
マスの位置を表すために、各マスには列番号と行番号が割り当てられている。
列番号が x、行番号が y のマスは(x, y)で表される。左上隅がマス(0, 0)、右下隅がマス(W-1, H-1)である。
Ｂ君はキャラクターのボムボム君を動かして、ゲームのクリアを目指す。
ボムボム君は、最初スタート地点のマス（0, 0）にいる。盤面上にいる全ての敵を倒すとゲームクリアとなる。
敵が動くことはないが、ボムボム君は、以下の２種類の行動を何度でもとることができる。

• 上下左右の方向へ１マス動く。ただし、盤面の外に出てはいけない。
• 爆弾を使用し、自分がいるマスと列番号が同じマスにいる敵と、行番号が同じマスにいる敵を一掃する。

ボムボム君は 1 マス動くためにコスト１を消費する。
爆弾の使用回数に制限はなく、爆弾を使用するコストは発生しない。
また、ボムボム君は爆弾の影響を受けることはなく、敵がいるマスにも移動することができる。

課題

盤面の大きさと敵の情報が与えられたとき、ボムボム君が全ての敵を倒すための最小のコストを出力するプログラムを作成せよ。

入力

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

W H N
x1 y1
x2 y2
:
xN yN

１行目に盤面の左右方向のマスの数W(1≦W≦10⁵)、上下方向のマスの数H(1≦H≦10⁵)、敵の数N(1≦N≦10⁵)が与えられる。
続くN行に、i番目の敵がいるマスの列番号x_i(0≦x_i≦W-1)と行番号y_i(0≦y_i≦H-1)が与えられる。
同じマスに複数の敵がいることはない。

出力

最小のコストを１行に出力する。

入出力例

入力例1

5 4 4
0 3
1 1
2 2
2 3

出力例1

2

入力例2

6 6 5
2 1
5 2
3 3
1 4
1 5

出力例2

4

入力例3

8 8 4
6 0
7 0
0 6
0 7

出力例3

0