F - 在网格上的车

得分：600分

问题描述

我们有一个由 $H$ 行和 $W$ 列组成的网格。令方格 $(i,j)$ 表示位于第 $i$ 行和第 $j$ 列的方格。

网格上有 $M$ 个障碍物。第 $i$ 个障碍物位于方格 $(X_i, Y_i)$。

我们有一个车，车是国际象棋中的棋子，在方格 $(1,1)$ 上。在一步内，它可以沿着任意数量的无障碍物的方格向右或向下移动。

找出车在两步或两步之内能够到达的方格数。

约束

• $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$

输出

输出车能够在两步或两步之内到达的方格数。

4 3 2
2 2
3 3

10

除了障碍物方格外，每个方格都可以在两步或两步之内到达。

5 4 4
3 2
3 4
4 2
5 2

14

除了方格 $(4,4)$ 和 $(5,4)$ 之外的所有方格都可以在两步或两步之内到达。

200000 200000 0

40000000000