2728 「JOI 2015 Final」城墙

译自 JOI 2015 Final T5「城壁」

历史学家 JOI 教授对曾经存在过的 IOI 王国进行了研究。

根据过去的调查，IOI 王国的形状为由 $H$ 行，$W$ 列的格子组成的长方形。IOI 王国的首都为了防卫外敌入侵而修筑了一座城墙。

围住 IOI 王国首都的城墙形状如以下叙述：城墙形状由城墙的大小决定。大小为 $s(s\ge 3)$ 的城墙，指 $s\times s$ 的正方形的最外一圈，也就是除去此正方形中心 $(s-2)\times (s-2)$ 的小正方形剩下的区域。

据调查，围住首都的城墙的大小在 $L$ 或以上。而且已知 IOI 王国中的一些格子不存在城墙。

JOI 教授为了进一步研究，想要知道城墙有多少种可能的情况。

任务

给出 IOI 王国的大小，城墙的大小的最小值，和一些已知不存在城墙的格子，请编写程序求出城墙可能的情况数。

输入标准如下： - 第一行为四个以空格分开的整数 $H,W,L,P$。分别表示 IOI 王国的形状为纵 $H$ 行横 $W$ 行的由格子构成的长方形，城墙的大小在 $L$ 或以上，已知不存在城墙的格子有 $P$ 个；
- 接下来 $P$ 行中第 $i$ 行 $(1\le i\le P)$ 为两个以空格分开的整数 $A_i,B_i$。表示已知 IOI 王国从上数第 $A_i$ 行，从左数第 $B_i$ 行的格子不存在城墙。

输出一行：表示城墙情况总数的一个整数。

在样例 $1$ 的情况下，城墙有以下 $4$ 种情况。画 $\times$ 的格子表示已知不存在城墙的格子。

对于 $4\%$ 的分值： - $H\le 500$ - $W\le 500$

对于另 $16\%$ 的分值： - $0\le P\le 10$

对于 $100\%$ 的数据，所有输入满足以下条件： - $1\le H\le 4000$ - $1\le W\le 4000$ - $3\le L\le H$ 且 $3\le L\le W$ - $0\le P\le 10^5$ - $1\le A_i\le H(1\le i\le P)$ - $1\le B_i\le W(1\le i\le P)$ - $(A_i,B_i)\not =(A_j,B_j)(1\le i\lt j\le P)$