WC '07 P5 - BitStrings

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
Woburn Team Practice '07

A cow has just issued you a challenge! You are given a list of N (1
\le N \le 100) possibly empty bitstrings (strings consisting of only 0s and 1s), whose lengths do not exceed 50. You are also given n_{0} zeroes (0 \le n_{0} \le 300) and n_{1} ones (0 \le n_{1} \le 300) at your disposal. The cow wants to know the maximum number of bitstrings in the list that you can create using those 0s and 1s. Of course, once you use a 0 or 1, you cannot use it again.

Input Specification

The first line of the input file contains a single integer T (1 \le T
\le 10), indicating the number of testcases to follow.

Each testcase begins with a single line listing the integers N, n_{0}, and n_{1} as described above. The next N lines list the bitstrings in your list. The bitstrings don't appear in any particular order, and may contain duplicates.

Output Specification

Output the following (on separate lines) for each test case:

A single integer that is the maximum number of bitstrings you can create.

Sample Input

2
3 3 1
00
1
100
3 2 4
00
101
110

Sample Output

2
2

Explanation

Case 1: You can create the first two bitstrings in the list.
Case 2: Make the last two bitstrings this time!


Comments

There are no comments at the moment.