题目描述

Paul 正在乐团里。弦乐组被排列成一个 $r \times c$ 的矩形网格，除了 $n$ 个中提琴手外，其余都是小提琴手。Paul 非常喜欢中提琴，因此他希望能拍摄一张至少包含 $k$ 个中提琴手的照片。Paul 可以拍摄乐团中任意一个与坐标轴平行的矩形区域。请你计算 Paul 能拍摄的符合要求的不同照片数量。

如果两个照片对应的矩形区域的坐标不同，则它们被视为不同的照片。

输入格式

输入的第一行包含四个用空格分隔的整数 $r$、$c$、$n$、$k$（$1 \leq r, c, n \leq 10$，$1 \leq k \leq n$），分别表示弦乐组的行数、列数、中提琴数量，以及 Paul 至少希望照片中包含的中提琴数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i \leq r$，$1 \leq y_i \leq c$），表示第 $i$ 个中提琴手所在的位置。保证输入中同一个位置不会重复出现。

输出格式

输出一个整数，表示 Paul 能拍到包括至少 $k$ 个中提琴手的照片数量。

说明/提示

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

在第一个样例中，乐团的分布如下：

* #
*
*

Paul 可以只拍摄中提琴所在的单元格，也可以拍摄包含中提琴所在单元格的 $1 \times 2$ 的列，$2 \times 1$ 的行，或者整个区域，共有 $4$ 张不同的照片。

在第二个样例中，乐团的分布如下：

# * * # # *

在这种情况下，Paul 只能拍摄整个区域的一张照片。

在第三个样例中，乐团分布同第二个样例。

由 ChatGPT 5 翻译

样例

2 2 1 1
1 2

4

3 2 3 3
1 1
3 1
2 2

1

3 2 3 2
1 1
3 1
2 2

4