ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 H: 乐队

内存限制：128 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：8 通过：5
返回比赛提交提交记录

题目描述

Paul在管弦乐队。弦乐部分排列在一个 r×c 的矩形网格中，除 n 个中提琴手外，其余都是小提琴手。Paul真的很喜欢中提琴，所以他想拍一张至少包括 k 根中提琴的照片。Paul可以拍下管弦乐队中任何轴平行的矩形。计算 Paul 可以拍的照片的数量。

    如果对应矩形的坐标不同，则认为两张图片不同。
Paul is at the orchestra. The string section is arranged in an r×c rectangular grid and is filled with violinists with the exception of n violists. Paul really likes violas, so he would like to take a picture including at least k of them. Paul can take a picture of any axis-parallel rectangle in the orchestra. Count the number of possible pictures that Paul can take.
Two pictures are considered to be different if the coordinates of corresponding rectangles are different.

Input
The first line of input contains four space-separated integers r, c, n, k (1≤r,c,n≤10, 1≤k≤n)− the number of rows and columns of the string section, the total number of violas, and the minimum number of violas Paul would like in his photograph, respectively.
The next n lines each contain two integers xi and yi (1≤xi≤r, 1≤yi≤c): the position of the i-th viola. It is guaranteed that no location appears more than once in the input.
Output
Print a single integer− the number of photographs Paul can take which include at least k violas.
Examples
Input 
2 2 1 1
1 2
Output 
4
Input 
3 2 3 3
1 1
3 1
2 2
Output 
1
Input 
3 2 3 2
1 1
3 1
2 2
Output 
4
Note
We will use '*' to denote violinists and '#' to denote violists.
In the first sample, the orchestra looks as follows 
*#
**
Paul can take a photograph of just the viola, the 1×2 column containing the viola, the 2×1 row containing the viola, or the entire string section, for 4 pictures total. In the second sample, the orchestra looks as follows 
#*
*#
#*
Paul must take a photograph of the entire section. In the third sample, the orchestra looks the same as in the second sample.

输入格式

第一行input包含四个空格分隔的整数r,c,n,k(1≤r,c,n≤10,1≤k≤n)−字符串部分的行数和列数，总数中提琴的数量，以及Paul希望在他的照片中出现的最少中提琴数量。
接下来n行每行包含两个整数xi和yi（1≤xi≤r，1≤yi≤c）：第i把中提琴的位置。保证没有位置在输入中出现超过一次。

输出格式

打印一个整数——Paul可以拍摄的至少包括 k 中提琴的照片数量。
Examples
Input 
2 2 1 1
1 2
Output 
4
Input 
3 2 3 3
1 1
3 1
2 2
Output 
1
Input 
3 2 3 2
1 1
3 1
2 2
Output 
4

输入样例 复制 

2 2 1 1
1 2

输出样例 复制 

4

数据范围与提示

我们将用“*”表示小提琴手，用“#”表示中提琴手。

在第一个示例中，管弦乐队看起来如下所示

* #

**

Paul可以只拍摄中提琴的照片，1×2列包含中提琴，2×1行包含中提琴，或整个弦乐部分，总共4张照片。在第二个样本中，管弦乐队是这样的

# *

* #

# *

保罗必须拍下整个区域的照片。在第三个样本中，管弦乐队看起来和第二个样本中一样。

分类标签