当前没有测试数据。

题目描述

西西家的客厅非常大，可以视为由 $N \times M$ 个小正方形组成的网格，每个位置按所在行和列的编号标记，账号从$1$开始。

当然客厅并不是完全空旷的，其中有 $K$ 个承重柱，第 $i$ 个柱子占据了 $(X\_i, Y\_i)$ 处的位置。

现在西西想买一条长度为 $L$，宽度为 $1$ 的餐桌，放置在客厅中。 要求桌子必须与房间的某一圈墙平行，并且恰好完整占据 $L$ 个空位，也即不允许与墙体或柱子相交（但可以贴着）。

换句话说，桌子必须“水平”或“垂直”摆放，且避开所有柱子，计算所有满足条件的摆放位置的方案数。

输入格式

第一行四个整数 $N, M, K, L$，表示房间的规模，柱子的数量，以及桌子的长度。 接下来 $K$ 行，每行两个整数 $X\_i, Y\_i$，表示每个柱子的位置。

输出格式

输出一行，一个整数，表示合法的摆放桌子的总方案数。

样例

【样例 1 输入】

5 6 0 5

【样例 1 输出】

16

【样例 1 解释】

水平摆放的话，每一行有 $2$ 种可能，共 $5$ 行。 垂直摆放的话，每一列有 $1$ 种可能，共 $6$ 列。 因此总共有 $2 \times 5 + 1 \times 6 = 16$ 种摆放方式。

【样例 2 输入】

5 6 2 4
2 2
2 5

【样例 2 输出】

20

【样例 2 解释】

餐厅的地图表示如下，可以尝试自己数一数

.o..o.
......
......
......
......

【样例 3/4】

见附加文件table.zip

数据范围与提示

所有测试数据的范围和特点如下表所示：

对于所有测试点，保证 $1 \le N, M \le 10^9$，$0 \le K \le 10^5$，$2 \le L \le 10^9$，$K \le NM$，$1 \le X\_i \le N$，$1 \le Y\_i \le M$。