保罗在管弦乐队中。弦乐部分排列成 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
注意
我们将使用“*”表示小提琴手,使用“#”表示中提琴手。
在第一个示例中,管弦乐队如下所示:
在第二个示例中,管弦乐队如下所示:
在第三个样本中,管弦乐队看起来与第二个样本中的相同。