ダンジョン

Ｂ君は人気のゲーム「ダンジョン」で遊んでいる。ゲームは、W × H 個のマス目状に区切られた長方形の盤面上で行われる。マスの位置を表すために、各マスには列番号と行番号が割り当てられている。列番号がx、行番号がy のマスは(x, y)で表される。左上隅がマス(0, 0)、右下隅がマス(W-1, H-1)である。

Ｂ君はキャラクターのボムボム君を動かして、ゲームのクリアを目指す。ボムボム君は、最初スタート地点のマス（0, 0）にいる。盤面上にいる全ての敵を倒すとゲームクリアとなる。敵が動くことはないが、ボムボム君は、以下の２種類の行動を何度でもとることができる。

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

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

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

Input

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

W H N
x_1 y_1
x_2 y_2
:
x_N y_N

１行目に盤面の左右方向のマスの数 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) が与えられる。同じマスに複数の敵がいることはない。

Output

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

Sample Input 1

5 4 4
0 3
1 1
2 2
2 3

Sample Output 1

2

Sample Input 2

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

Sample Output 2

4

Sample Input 3

8 8 4
6 0
7 0
0 6
0 7

Sample Output 3

0

Note

Algorithm

 

C++

 

---