问题描述

具体描述见教材p89：i 行放一个炸弹，第 i 行的怪物就被杀死了，现有r行c列的草坪，有n只怪物，怪物不移动，给 k 个炸弹，要求出用 k 个炸弹最多能杀死多少只怪物？游戏，简单排序

格式

输入

第1行，四个正整数$r, c, k, n$; 接下来 $n$ 行，每二两个正整数$x,y$，表示第$x$行的第$y$列中有一个怪物。

输出

第1行，可以杀死的怪物数。 第2行按顺序输出所有被灭的行（如果多种不同方案，输出 字典序小的那种）。 注：样例说明，可以杀死1行和4行的所有怪物，方案(1,4), (2,4),(3,4)都可以杀死一样多，但(1,4)字典序小。

样例

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

4
1 4

限制

1s, 64MB.