题目描述

小 C 正在用彩铅给一张 $n$ 行 $m$ 列的方格纸涂色。初始时，所有方格都是空白的。

他一共要进行 $q$ 次涂色，每次涂色会选取一行或一列，给这一行或这一列的所有方格都添加 $1$ 层颜色。

小 C 喜欢浅色，所以他会在每次涂色结束后，把所有恰好被涂上 $k$ 层颜色的方格的颜色都擦掉，让这些方格重新变成空白的。

小 C 想知道，最终共有多少方格被涂上了颜色。

输入格式

第一行包含四个整数 $n,m,q,k$。

接下来 $q$ 行，每行包含两个整数 $op,x$：

• 若 $op = 1$，则表示给第 $x$ 行的所有方格添加 $1$ 层颜色；
• 若 $op = 2$，则表示给第 $x$ 列的所有方格添加 $1$ 层颜色。

输出格式

输出一行一个整数，表示最终有颜色的方格数量。

样例

3 4 5 3
1 3
2 4
1 2
1 3
2 2

8

样例解释

初始空白，$k=3$。

1. 第 $3$ 行加 $1$ 层：第 $3$ 行所有格子变为 $1$ 层。
2. 第 $4$ 列加 $1$ 层：第 $4$ 列所有格子增加 $1$ 层，其中 $(3,4)$ 变为 $2$ 层。
3. 第 $2$ 行加 $1$ 层：第 $2$ 行所有格子增加 $1$ 层，其中 $(2,4)$ 变为 $2$ 层（原来列 $4$ 有 $1$ 层）。
4. 第 $3$ 行加 $1$ 层：第 $3$ 行所有格子增加 $1$ 层，此时 $(3,4)$ 达到 $3$ 层，恰好等于 $k$，被擦除变空白。$(3,1),(3,2),(3,3)$ 变为 $2$ 层。
5. 第 $2$ 列加 $1$ 层：第 $2$ 列所有格子增加 $1$ 层，此时 $(3,2)$ 从 $2$ 变为 $3$ 层，等于 $k$，被擦除。其他格子层数增加。

最终有颜色的格子为：$(1,2),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,3)$，共 $8$ 个。

数据范围与提示

• 对于 $40\%$ 的数据：$1 \le n,m \le 3\times10^3$，$1 \le k \le q \le 3\times10^3$；
• 对于 $100\%$ 的数据：$1 \le n,m \le 2\times10^5$，$1 \le k \le q \le 5\times10^5$。

来源

CSPJ-重点算法班