题目描述

译自 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$ 行的格子不存在城墙。

输出格式

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

5 5 3 2
2 2
4 3

4

7 8 4 3
2 2
3 7
6 5

13

4000 4000 1234 4
1161 3028
596 1892
3731 2606
702 1530

7050792912

数据范围与提示

对于 $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)$