题目描述

译自 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

输入

5 5 3 2
2 2
4 3

输出

4

样例 2

输入

7 8 4 3
2 2
3 7
6 5

输出

13

---

样例 3

输入

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