当前没有测试数据。

题面翻译

给出一个 $H\times W$ 的矩阵，每个位置要么有洞，要么没洞，问有多少个每个元素均为正整数的三元组 $(x,y,n)$，满足：

$x+n-1\le H$，$y+n-1\le W$，以 $(x,y)$ 为左上角、$(x+n-1,y+n-1)$ 为右下角的矩阵每个位置都没有洞。

$H,W\le 3000$，洞的个数不超过 $10^5$。

题目描述

縦 $H$ 行, 横 $W$ 列のグリッドがあります。グリッドの上から $i$ 行目, 左から $j$ 列目のマスを $(i,\ j)$ と呼びます。 グリッドの各マスは穴の空いたマスとそうでないマスのどちらかです。穴が空いたマスは $(a_1,\ b_1),\ (a_2,\ b_2),\ \dots,\ (a_N,\ b_N)$ のちょうど $N$ マスです。

正整数の組 $(i,\ j,\ n)$ が次の条件を満たすとき、$(i,\ j)$ を左上隅, $(i\ +\ n\ -\ 1,\ j\ +\ n\ -\ 1)$ を右下隅とする正方形領域を 穴のない正方形 と呼びます。

• $i\ +\ n\ -\ 1\ \leq\ H$
• $j\ +\ n\ -\ 1\ \leq\ W$
• $ 0\ \leq\ k\ \leq\ n\ -\ 1,\ 0\ \leq\ l\ \leq\ n\ -\ 1 $ を満たす全ての非負整数の組 $(k,\ l)$ に対して、$(i\ +\ k,\ j\ +\ l)$ は穴が空いていないマスである。

グリッド内に穴のない正方形は何個ありますか？

输入格式

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

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

输出格式

穴のない正方形の個数を出力せよ。

样例 #1

样例输入 #1

2 3 1
2 3

样例输出 #1

6

样例 #2

样例输入 #2

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

样例输出 #2

0

样例 #3

样例输入 #3

1 1 0

样例输出 #3

1

样例 #4

样例输入 #4

3000 3000 0

样例输出 #4

9004500500

提示

制約

• $1\ \leq\ H,\ W\ \leq\ 3000$
• $0\ \leq\ N\ \leq\ \min(H\ \times\ W,\ 10^5)$
• $1\ \leq\ a_i\ \leq\ H$
• $1\ \leq\ b_i\ \leq\ W$
• $(a_i,\ b_i)$ は互いに異なる
• 入力される値は全て整数

Sample Explanation 1

穴のない正方形は全部で $6$ 個あります。 それらを列挙すると次の通りです。このうちはじめの $5$ 個は $n\ =\ 1$ の場合であり、領域の左上隅のマスと右下隅のマスが一致します。 - $(1,\ 1)$ を左上隅かつ右下隅とする正方形領域 - $(1,\ 2)$ を左上隅かつ右下隅とする正方形領域 - $(1,\ 3)$ を左上隅かつ右下隅とする正方形領域 - $(2,\ 1)$ を左上隅かつ右下隅とする正方形領域 - $(2,\ 2)$ を左上隅かつ右下隅とする正方形領域 - $(1,\ 1)$ を左上隅, $(2,\ 2)$ を右下隅とする正方形領域

Sample Explanation 2

穴のない正方形が存在しない場合もあります。

Sample Explanation 3

穴のない正方形がグリッド全体と一致する場合もあります。