AT_abc023_c.[ABC023C] 収集王

高桥君计划移动到某个房间。

该房间由 $R$ 行 $C$ 列的正方形格子组成。我们将第 $i\ (1\leq i\leq R)$ 行第 $j\ (1\leq j\leq C)$ 列的格子称为格子 $(i,j)$。

这些格子中总共有 $N$ 颗糖果。每颗糖果编号为 $1$ 到 $N$，糖果 $i\ (1\leq i\leq N)$ 放在格子 $(r_i,c_i)$ 上。任意两颗糖果不会放在同一个格子上。

高桥君可以选择移动到任意一个格子。移动后，他会按照如下方式获得糖果：

• 首先，他会获得与他所在格子同一行的所有格子上的糖果。
• 然后，他会获得与他所在格子同一列的所有格子上的糖果。

高桥君不会进行其他操作。

高桥君希望获得的糖果数量恰好为 $K$。请你计算，有多少个格子作为移动目标可以满足获得的糖果数量恰好为 $K$。

输入从标准输入按以下格式给出。

$R$ $C$ $K$
$N$
$r_1$ $c_1$
$r_2$ $c_2$
$\vdots$
$r_N$ $c_N$

• 第 $1$ 行包含三个整数 $R\ (1\leq R\leq 100\,000)$，$C\ (1\leq C\leq 100\,000)$，$K\ (1\leq K\leq 100\,000)$，表示房间有 $R$ 行 $C$ 列，$K$ 是高桥君想要获得的糖果数量。
• 第 $2$ 行包含一个整数 $N\ (K\leq N\leq 100\,000)$，表示糖果的总数。
• 接下来的 $N$ 行，每行包含两个整数 $r_i\ (1\leq r_i\leq R)$，$c_i\ (1\leq c_i\leq C)$，表示第 $i$ 颗糖果在格子 $(r_i,c_i)$ 上。
• 对于 $i\neq j$，有 $(r_i,c_i)\neq(r_j,c_j)$。

输出恰好能获得 $K$ 颗糖果的移动目标格子的总数。输出后需换行。

部分分

本题设置了部分分。

• 若数据满足 $R\leq 50$ 且 $C\leq 50$ 且 $N\leq 50$，则该数据集 $1$ 满足条件可得 $30$ 分。
• 若无额外限制的数据集 $2$ 满足条件，则可再得 $70$ 分。

样例解释 1

例如，考虑高桥君移动到格子 $(3,2)$ 的情况。

• 糖果 $1$ 在格子 $(1,2)$。该格子与 $(3,2)$ 在同一列，所以高桥君可以获得糖果 $1$。
• 糖果 $2$ 在格子 $(2,1)$。该格子与 $(3,2)$ 不在同一行也不在同一列，所以高桥君无法获得糖果 $2$。
• 糖果 $3$ 在格子 $(2,5)$。该格子与 $(3,2)$ 不在同一行也不在同一列，所以高桥君无法获得糖果 $3$。
• 糖果 $4$ 在格子 $(3,2)$。该格子与 $(3,2)$ 在同一个格子（同一行且同一列），所以高桥君可以获得糖果 $4$。
• 糖果 $5$ 在格子 $(3,5)$。该格子与 $(3,2)$ 在同一行，所以高桥君可以获得糖果 $5$。

因此，高桥君可以获得糖果 $1$、$4$、$5$，共 $3$ 颗糖果，正好等于 $K$，所以格子 $(3,2)$ 是一个满足条件的目标格子。
此外，格子 $(1,5)$、$(2,5)$、$(3,1)$、$(3,5)$ 也满足条件，所以答案为 $5$。

样例解释 2

无论移动到哪个格子，都无法恰好获得 $1$ 颗糖果。

由 ChatGPT 4.1 翻译