问题 E: 二进制字符串背包问题

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:10 解决:6

题目描述

小明正在学习动态规划算法,他遇到了一个有趣的背包问题。给定一个由二进制字符串组成的数组和两个整数m、n,需要找出最大子集的长度,使得该子集中最多包含m个'0'和n个'1'。
这个问题可以看作是一个二维费用的01背包问题,每个字符串都有两个"重量":包含的'0'的数量和'1'的数量,而我们的"背包容量"分别是m和n。

输入

第一行: 三个整数 k、m、n

k:二进制字符串的数量 (1 ≤ k ≤ 600)

m:最多可以包含的'0'的数量 (1 ≤ m ≤ 100)
n:最多可以包含的'1'的数量 (1 ≤ n ≤ 100)

接下来k行: 每行一个二进制字符串

每个字符串长度不超过100

字符串仅由'0'和'1'组成

输出

输出一个整数,表示满足条件的最大子集的长度。

样例输入 复制

5 5 3
10
0001
111001
1
0

样例输出 复制

4

提示

1 ≤ k ≤ 600
1 ≤ 每个字符串长度 ≤ 100
1 ≤ m, n ≤ 100
字符串仅包含'0'和'1'