无洞正方形

题目描述

有一个 $H$ 行 $W$ 列的网格。用 $(i, j)$ 表示该网格第 $i$ 行(从上往下数)、第 $j$ 列(从左往右数)的格子。

网格中的每个格子要么有洞,要么没有洞。恰好有 $N$ 个格子有洞,分别是 $(a_1, b_1), (a_2, b_2), \dots, (a_N, b_N)$。

当正整数三元组 $(i, j, n)$ 满足以下条件时,称以 $(i, j)$ 为左上角、以 $(i + n - 1, j + n - 1)$ 为右下角的正方形区域为无洞正方形:

• $i + n - 1 \le H$
• $j + n - 1 \le W$
• 对所有满足 $0 \le k \le n - 1$、$0 \le l \le n - 1$ 的非负整数对 $(k, l)$,格子 $(i + k, j + l)$ 都没有洞。

网格中共有多少个无洞正方形?

输入格式

输入按以下格式从标准输入给出:

$H$ $W$ $N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_N$ $b_N$

输出格式

输出无洞正方形的数量。

样例

2 3 1
2 3

6

共有六个无洞正方形,列举如下。前五个满足 $n = 1$,左上角和右下角是同一个格子。

• 左上角和右下角都为 $(1, 1)$ 的正方形区域。
• 左上角和右下角都为 $(1, 2)$ 的正方形区域。
• 左上角和右下角都为 $(1, 3)$ 的正方形区域。
• 左上角和右下角都为 $(2, 1)$ 的正方形区域。
• 左上角和右下角都为 $(2, 2)$ 的正方形区域。
• 左上角为 $(1, 1)$、右下角为 $(2, 2)$ 的正方形区域。

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

0

也可能不存在无洞正方形。

1 1 0

1

整个网格也可以是一个无洞正方形。

3000 3000 0

9004500500

数据范围

• $1 \le H, W \le 3000$
• $0 \le N \le \min(H \times W, 10^5)$
• $1 \le a_i \le H$
• $1 \le b_i \le W$
• 所有的 $(a_i, b_i)$ 两两不同。
• 输入中的所有值均为整数。