3014 - 找最多的串串

给定一个集合S,共有k元素,集合的每个元素是由0和1组成的串。

现要求从中选出一些串,形成新的集合S1。这个新集合S1需要满足这样的条件:它所有串中0的个数之和不超过m,1的个数之和不超过n。

问你S1的元素个数最多是多少。

提示:从S中选择串放到S1中时,一个串只能选一次。

输入

第一行包含四个整数,k、r、m、n。k表示S中元素个数,r表示最长01串的长度,m表示0的个数的上限,n表示1的个数的上限。

后面后k行,每一行是一个01串。

输出

S1中最多包含S中的多少个01串。

样例

输入

5 6 5 3
10
0001
111001
1
0

输出

4

输入

3 2 1 1
10
1
0

输出

2

提示

对于30%的数据,保证有k<=20,r<=20,m<=100,n<=100;

对于60%的数据,保证有k<=300,r<=50,m<=500,n<=500;

对于全部的数据,保证有k<=1000,r<=100,m<=2000,n<=2000.

来源

本站月赛

时间限制 10 秒
内存限制 256 MB
讨论 统计
上一题 下一题