配点: 100 点
历史学家JOI教授正在研究曾经存在的IOI王国。
根据以往的研究,IOI王国是 H 行,横 W 它具有矩形形状,分为单元列。 IOI王国的首都被城墙包围以进行防御。
IOI王国首都周围的城墙具有以下形状。城堡墙有一个固定值,称为其尺寸。尺寸 s (s \geqq 3) 的城墙是什么? 从s \times s 除外周以外的正方形区域 (s - 2) \times (s - 2) 删除了方形区域。
据考证,首都周围的城墙尺寸为 L 就是这样。据了解,IOI王国的一些广场上没有城墙。
JOI教授想知道有多少种可能的城墙可供进一步研究。
課題
IOI 给定王国的大小、城墙的最小尺寸以及已知不存在城墙的方格的信息,编写一个程序来找出可能有多少个城墙。
入力
从标准输入读取以下数据。
- 1 行包含一个整数 H, W, L, P 以空格作为分隔符。这意味着IOI王国是 H 行,横 W 它有一个长方形的形状,分为正方形的柱子,城堡墙的大小是 L 仅此而已,已知城墙不存在的方格是 P 表示存在一个正方形。
- 继续 P 行 i 行目 (1 \leqq i \leqq P) 是一个整数 A_i, B_i 以空格作为分隔符。这是来自IOI王国之上。 A_i 线,从左起 B_i 表示已知该列中的方格内没有城墙。
出力
表示可能的城堡墙数量的整数被发送到标准输出。 输出为 1 行。
制限
所有输入数据满足以下条件。
- 1 \leqq H \leqq 4\,000.
- 1 \leqq W \leqq 4\,000.
- 3 \leqq L \leqq H 和 满足 3 \leqq L \leqq W.
- 0 \leqq P \leqq 100\,000.
- 1 \leqq A_i \leqq H (1 \leqq i \leqq P).
- 1 \leqq B_i \leqq W (1 \leqq i \leqq P).
- (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq P).
小課題
小課題 1 [4 点]
满足以下条件。
- H \leqq 500.
- W \leqq 500.
小課題 2 [16 点]
- 0 \leqq P \leqq 10 满意。
小課題 3 [80 点]
没有其他限制。
入力例 1
5 5 3 2 2 2 4 3
出力例 1
4
在此输入示例中,可能的城堡墙如下: 4 以下是可能的。然而,× 指示的方格是已知没有城墙的方格。

入力例 2
7 8 4 3 2 2 3 7 6 5
出力例 2
13
入力例 3
4000 4000 1234 4 1161 3028 596 1892 3731 2606 702 1530
出力例 3
7050792912