CF627E Orchestra

Paul 在音乐厅的弦乐部分。弦乐部分以 $r\times c$ 的矩形网格排布，除了 $n$ 个中提琴手以外，其余都是小提琴手。Paul 非常喜欢中提琴，所以他希望拍一张包含至少 $k$ 个中提琴手的照片。Paul 可以拍摄任意一个与坐标轴平行的矩形区域。 请你计算 Paul 可以拍的符合要求的照片数量。 如果两个照片所对应的矩形区域的坐标不同，则它们被认为是不同的照片。

输入的第一行包含四个用空格分隔的整数 $r$、$c$、$n$、$k$（$1 \leq r, c, n \leq 3000$，$1 \leq k \leq \min(n, 10)$），分别表示弦乐部分的行数、列数、中提琴手的总数以及 Paul 希望照片中至少包含的中提琴手数量。 接下来的 $n$ 行每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i \leq r$，$1 \leq y_i \leq c$），表示第 $i$ 个中提琴手的位置。保证输入中不存在重复的位置。

输出一个整数，表示 Paul 可以拍摄的包含至少 $k$ 个中提琴手的照片数量。

我们用 '\*' 表示小提琴手，用 '\#' 表示中提琴手。 在第一个样例中，乐队排布如下： `*#` `**` Paul 可以拍摄仅包含中提琴手的区域、包含该中提琴手的 $1\times2$ 柱状区域、包含该中提琴手的 $2\times1$ 行状区域，以及整个弦乐区，一共 $4$ 种。 在第二个样例中，乐队排布如下： `#*` `*#` `#*` Paul 必须拍摄整个弦乐区。 在第三个样例中，乐队的排布与第二个样例相同。 由 ChatGPT 5 翻译