配点 : $600$ 点

問題文

縦 $H$ マス、横 $W$ マスのグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と表します。

グリッド上には $M$ 個の障害物があり、$i$ 番目の障害物はマス $(X_i,Y_i)$ に置かれています。

マス $(1,1)$ に飛車の駒が置いてあります。飛車の駒は、今いる位置から右または下方向に伸びる直線上にあり、障害物を飛び越えずに到達できるマスに $1$ 手で移動することができます。

$2$ 手以内の移動で飛車の駒が到達できるマスの数を求めてください。

制約

• $1\leq H,W \leq 2\times 10^5$
• $0\leq M \leq 2\times 10^5$
• $1\leq X_i \leq H$
• $1\leq Y_i \leq W$
• $(X_i,Y_i) \neq (1,1)$
• $(X_i,Y_i)$ は相異なる
• 入力は全て整数

入力

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

$H$ $W$ $M$

$X_1$ $Y_1$

$\vdots$

$X_M$ $Y_M$

出力

$2$ 手以内の移動で飛車の駒が到達できるマスの数を出力せよ。

4 3 2
2 2
3 3

10

障害物のない全てのマスに $2$ 手以内で移動できます。

5 4 4
3 2
3 4
4 2
5 2

14

障害物のないマスのうち、$(4,4),(5,4)$ 以外の全てのマスに $2$ 手以内で移動できます。

200000 200000 0

40000000000