AT_joi2015ho_e 城壁 (Rampart)

历史学者 JOI 教授正在研究曾经存在的 IOI 王国。 根据以往的调查，IOI 王国呈现为一个被划分为纵向 $H$ 行、横向 $W$ 列的矩形区域。IOI 王国的首都为了防御，被城墙包围着。 IOI 王国首都的城墙形状如下所述。城墙有一个被称为“大小”的数值。大小为 $s$（$s \geq 3$）的城墙，是指从 $s \times s$ 的正方形区域中，去除内部的 $(s-2) \times (s-2)$ 的正方形区域后剩下的部分。 调查显示，首都城墙的大小至少为 $L$。此外，已知 IOI 王国的某些格子上没有城墙。 JOI 教授为了进一步研究，想知道作为城墙可能存在的方案有多少种。

请从标准输入读取以下数据。 - 第 $1$ 行包含四个整数 $H,\ W,\ L,\ P$，用空格隔开。表示 IOI 王国被划分为 $H$ 行 $W$ 列的矩形，城墙的大小至少为 $L$，并且有 $P$ 个格子已知没有城墙。 - 接下来的 $P$ 行中，第 $i$ 行（$1 \leq i \leq P$）包含两个整数 $A_i,\ B_i$，用空格隔开。表示从上到下第 $A_i$ 行，从左到右第 $B_i$ 列的格子已知没有城墙。

请输出一个整数，表示作为城墙可能存在的方案数。

## 任务 给定 IOI 王国的大小、城墙的最小大小，以及已知没有城墙的格子的信息，请编写程序，求出作为城墙可能存在的方案数。 ## 限制 所有输入数据满足以下条件。 - $1 \leq H \leq 4000$。 - $1 \leq W \leq 4000$。 - $3 \leq L \leq H$ 且 $3 \leq L \leq W$。 - $0 \leq P \leq 100\,000$。 - $1 \leq A_i \leq H$（$1 \leq i \leq P$）。 - $1 \leq B_i \leq W$（$1 \leq i \leq P$）。 - $(A_i, B_i) \neq (A_j, B_j)$（$1 \leq i < j \leq P$）。 ## 子任务 ### 子任务 1 [4 分] 满足以下条件。 - $H \leq 500$。 - $W \leq 500$。 ### 子任务 2 [16 分] - $0 \leq P \leq 10$。 ### 子任务 3 [80 分] 没有额外限制。 ## 样例解释 1 在此输入样例中，作为城墙可能存在的方案有以下 $4$ 种。用 `×` 表示已知没有城墙的格子。  ## 样例解释 2 - 由 ChatGPT 4.1 翻译