题目描述

植物大战僵尸这款游戏中，有一种植物武器叫辣椒炸弹，在草坪中的任意一格摆放它可以把草坪中该行上的所有僵尸瞬间消灭，也就是说，如果在第 $i$行中任意位置摆放一个炸弹，第 $i$行中的所有僵尸就瞬间都被杀死了。

现在我们假定草坪有 $r$行 $c$列，草坪中有 $n$只僵尸，僵尸不移动。现在给你 $k$个辣椒炸弹，要求只能使用这 $k$个炸弹来消灭这些僵尸，请问最多可以杀死多少只僵尸。

输入格式

第一行 $4$个正整数 $r,\ c,\ k,\ n$。

接下来 $n$行，每行两个正整数 $x,\ y$，表示第 $x$行的第 $y$列中有一只僵尸（可能存在同一个位置多只僵尸的情况）。

输出格式

第一行输出最多可以杀死的僵尸数。

第二行按顺序输出所有被消灭的行号，如果有多种方案，输出字典序最小的那种方案（行号从小到大输出即可）。

样例说明

第 $1$行 $1$只僵尸，第 $2$行 $1$只，第 $3$行 $1$只，第 $4$行 $3$只（位置 $(4,4),(4,5),(4,5)$共 $3$只）。

取第 $1$行+第 $4$行共杀 $1+3=4$只，是最优。$(2,4),(3,4)$也是 $4$只，但 $(1,4)$字典序最小。

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

4
1 4

数据规模与约定

对于 $30\%$数据：$0 < r,c \le 50$，$n \le 2500$

对于 $100\%$数据：$0 < r,c \le 1000$，$n \le 1000000$，$k \le r$