题目描述

植物大战僵尸这款游戏中，有一种植物武器叫辣椒炸弹，在草坪中的任意一格摆放它可以把草坪中该行上的所有僵尸消灭，也是说，如果在第i行中任意位置摆放一个炸弹，第i行中的所有僵尸就被杀死。现在我们假定草坪有r行c列，草坪中有n只僵尸，僵尸不移动，现在给你k个辣椒炸弹，要求只能使用这k个炸弹来消灭这些僵尸，请问最多可以杀死多少只僵尸。

输入格式

第一行4个正整数 r，c，k，n 接下来n行，每行两个正整数x，y，表示第x行的第y列有一只僵尸

输出格式

第一行输出最多可以杀死的僵尸数 第二行按顺序输出所有被消灭的行，如果有不同方案，输出字典序最小的那种方案。

输入输出样例

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

4
1 4

样例解释

方案(1,4) (2,4) (3,4)都是一样多的僵尸，但是(1,4)的字典序最小 对于30%的数据：0<r,c<=50, n<=2500 对于100%的数据：0<r,c<=1000, n<=1000000, k<=r