Dungeon

Time Limit : 1 sec, Memory Limit : 262144 KB

ダンジョン

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

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

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

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

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

Input

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

W H N
x_1 y_1
x_2 y_2
:
x_N y_N

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

Output

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

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

Source: PC Koshien 2017 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2017-9-9
http://web-ext.u-aizu.ac.jp/pc-concours/