该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个 $n$ 行 $m$ 列的网格，初始时每一个格子都是白色。露米娅需要用 $k$ 种不同的颜色（包括白色）对这个网格涂色 $q$ 次，涂色的规则是：露米娅可以选择任意一种颜色，将某一整行（或某一整列）涂上这种颜色，该行（或该列）格子原有的颜色都会被覆盖成新涂上的颜色。请你算一算涂完色后网格上最多会出现几种不同的颜色。

注：涂色的位置和顺序是固定的，但露米娅可以自由决定每次使用哪种颜色

输入格式

在文件 MoonlightRay.in 中读入。

第一行包含四个整数 $n,m,k,q$，分别表示网格的行数、列数，颜色的种类数以及露米娅进行涂色操作的次数。

接下来 $q$ 行，每行包含两个整数 $op_i,x_i$，表示一次操作。

• 如果 $op_i = 0$，那么这次操作会将第 $x_i$ 行涂色。
• 如果 $op_i = 1$，那么这次操作会将第 $x_i$ 列涂色。

输出格式

在文件 MoonlightRay.out 中输出。

输出一行一个整数表示答案。

样例

输入数据

3 3 3 2
0 1
1 1

输出数据

3

提示

数据范围与提示