WC '07 P5 - BitStrings

View as PDF

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 possibly empty bitstrings (strings consisting of only 0s and 1s), whose lengths do not exceed . You are also given zeroes and ones at your disposal. The cow wants to know the maximum number of bitstrings in the list that you can create using those s and s. Of course, once you use a or , you cannot use it again.

Input Specification

The first line of the input file contains a single integer , indicating the number of testcases to follow.

Each testcase begins with a single line listing the integers , , and as described above. The next 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 : You can create the first two bitstrings in the list.
Case : Make the last two bitstrings this time!