#2728. 「JOI 2015 Final」城墙

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hy1004

题目描述

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

输出样例 1

4

样例说明 1

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

09a21403b6ad516667cf908bd6d5dbb2.png

输入样例 2

7 8 4 3
2 2
3 7
6 5

输出样例 2

13

输入样例 3

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

输出样例 3

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)