题目描述

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

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

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

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

输入格式

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

$H$ $W$ $M$ $X_1$ $Y_1$ $\vdots$ $X_M$ $Y_M$

输出格式

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

题目大意

你有一个 $n$ 行 $m$ 列的地图，其中有 $k$ 个格子有障碍。有一只猴子在左上角，这只猴子一步可以向下或向右移动任意格（不能穿过障碍物）。

求猴子 $2$ 步内可以到达的格子数（也就是说可以走 $0,1,2$ 步）。

translated by

4 3 2
2 2
3 3

10

5 4 4
3 2
3 4
4 2
5 2

14

200000 200000 0

40000000000

提示

制約

• $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)$ は相異なる
• 入力は全て整数

Sample Explanation 1

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

Sample Explanation 2

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