← 返回题目列表

Codeforces · 627/E

E. 乐团

中文机器翻译题面 查看原题

保罗在管弦乐队中。弦乐部分排列成 r×c 矩形网格,除了 n 个中提琴手外,里面都是小提琴手。 Paul 非常喜欢中提琴,因此他想拍一张包含至少 k 个中提琴的照片。保罗可以拍摄管弦乐队中任何与轴平行的矩形的照片。计算保罗可以拍摄的照片数量。

如果两张图片对应的矩形坐标不同,则认为两张图片不同。

输入

输入的第一行包含四个空格分隔的整数 r, c, n, k (1 ≤ r, c, n ≤ 3000, 1 ≤ k ≤ min(n, 10)) - 分别是弦乐部分的行数和列数、中提琴的总数以及 Paul 希望在照片中保留的中提琴的最小数量。

接下来的 n 行每行包含两个整数 xi 和 yi (1 ≤ xi ≤ r, 1 ≤ yi ≤ c):第 i 个中提琴的位置。确保没有位置在输入中出现多次。

输出

打印一个整数 - Paul 可以拍摄的照片数量,其中至少包含 k 个中提琴。

示例

输入 #1

2 2 1 1
1 2

输出 #1

4

输入 #2

3 2 3 3
1 1
3 1
2 2

输出 #2

1

输入 #3

3 2 3 2
1 1
3 1
2 2

输出 #3

4

注意

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

在第一个示例中,管弦乐队如下所示:

在第二个示例中,管弦乐队如下所示:

在第三个样本中,管弦乐队看起来与第二个样本中的相同。