CF627E.Orchestra

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.

保罗正在交响乐团中。弦乐声部被排列成一个 $r \times c$ 的矩形网格，其中除 $n$ 名中提琴手外，其余均为小提琴手。保罗非常喜欢中提琴，因此他希望拍摄一张至少包含 $k$ 名中提琴手的照片。保罗可以拍摄乐团中任意一个与坐标轴平行的矩形区域。

请计算保罗可能拍摄的照片数量。

若两个矩形的坐标不同，则认为它们对应的照片不同。

The first line of input contains four space-separated integers r, c, n, k (1 ≤ r, c, n ≤ 3000, 1 ≤ k ≤ min(n, 10)) — 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 x__i and y__i (1 ≤ x__i ≤ r, 1 ≤ y__i ≤ c): the position of the i-th viola. It is guaranteed that no location appears more than once in the input.

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

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le r$，$1 \le y_i \le c$）：表示第 $i$ 把小提琴的位置。保证输入中任意位置不会重复出现。

Print a single integer — the number of photographs Paul can take which include at least k violas.

输出一个整数——保罗可以拍摄的、包含至少 k 把中提琴的照片数量。

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.

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

在第一个样例中，管弦乐队的排布如下：

*#
**

保罗可以仅拍摄中提琴所在的位置、包含该中提琴的 $1 \times 2$ 列、包含该中提琴的 $2 \times 1$ 行，或整个弦乐声部，共可拍摄 4 张照片。

在第二个样例中，管弦乐队的排布如下：

#*
*#
#*

保罗必须拍摄整个声部。

在第三个样例中，管弦乐队的排布与第二个样例完全相同。