飞车与网格

题目描述

有一个纵向 $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$ 步以内到达的格子数。

样例

4 3 2
2 2
3 3

10

可以移动到没有障碍物的所有格子。

5 4 4
3 2
3 4
4 2
5 2

14

在没有障碍物的格子中，除 $(4,4),(5,4)$ 外所有格子都能在 $2$ 步以内到达。

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)$ 互不相同
• 输入均为整数