题目描述

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

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

输入格式

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

接下来 n 行，每行两个正整数 x , y ，表示第 x 行的第 y 列中有一只僵尸。

数据范围

对于 30% 数据： r , c 不大于 50 , n 不大于 2500 ;

对于 100% 数据： r , c 不大于 1000 , n 不大于 1000000 , k 不大于 r

注意：在同一个位置有可能存在多个僵尸。

输出格式

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

第二行按行号从小到大输入所有消灭的行，如果有不同方案，输出字典序最小的那种方案。

样例

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

3
1 4

样例解释

样例说明：可以杀死第 1 行和第 4 行的所有僵尸，方案 (1,4) , (2,4) , (3,4) 都是一样多的僵尸，但方案 (1,4) 的字典序最小。