Woburn Team Practice '07

BitStrings

A cow has just issued you a challenge! You are given a list of N (1 ≤ N ≤ 100) possibly empty bitstrings (i.e., strings consisting of only 0s and 1s), whose lengths do not exceed 50. You are also given n₀ zeroes (0 ≤ n₀ ≤ 300) and n₁ ones (0 ≤ n₁ ≤ 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

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

Each testcase begins with a single line listing the integers N, n₀, and n₁ 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

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!

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Aug 25, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The test cases for this question are extremely weak.