30 世紀の初め以来、Country of Circles は世界最強の国となりました。西へ領土を拡大するため、Country of Rectangles への侵攻を計画しています。

Country of Rectangles の領土は $R\times C$ の表で表され、行には $1$ から $R$、列には $1$ から $C$ の番号が付いています。$i$ 行目、$j$ 列目のマスを $(i,j)$ と表します。

Country of Circles の国防省は、精鋭の空挺部隊を使って Country of Rectangles を攻撃する計画です。相手国にスパイを送り、Country of Rectangles の $N$ 個のマス $(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N)$ は守りが非常に弱く、容易に占領できることを知りました。そこで、次の計画を立てました。

• 初日には、この $N$ 個のマスそれぞれを占領するために空挺部隊の大隊を送ります。
• その後の各日には、それまでに占領したマスの少なくとも一つと辺を共有するすべてのマスを占領するために増援を送ります。

Country of Circles の軍は、望む任意のマスを占領できるほど強いと仮定します。

司令官は、国全体を征服するのに何日かかるか知りたいと考えています。

入力

• 最初の行には三つの整数 $R$, $C$, $N$ ($1\le R,C\le100$, $1\le N\le10\,000$) が与えられます。それぞれ Country of Rectangles の領土の行数、列数、守りの弱いマスの数です。これらのマスが相異なることは保証されません。
• 続く $N$ 行のうち $i$ 行目には二つの整数 $x_i$, $y_i$ ($1\le x_i\le R$, $1\le y_i\le C$) が与えられます。作戦初日に空挺部隊が送られる一つのマスを表します。

出力

Country of Circles が Country of Rectangles を完全に征服するのに必要な日数を、ちょうど一つの数として出力してください。

入出力例

入力 1

3 4 3
2 2
2 2
3 4

出力 1

3

注記

下図は、各日に計画がどのように実行されるかを示しています。

• 未占領のマスは白色です。
• 当日占領されたマスは縞模様で塗られています。
• それ以前の日に占領されたマスは単色で塗られています。

入力 2

2 3 6
1 1
1 2
1 3
2 1
2 2
2 3

出力 2

1