Magical Thinking v2

You and $N$ of your friends just took the B.A.T. (Binary Answer Test) to try to get into wizard school. The B.A.T. has $Q$ true-false questions, and each one is worth 1 point. You have no wizard powers, so you just picked arbitrary answers and hoped for the best.

The results of the test have already been sent out by quail mail, but the quail with your results has not arrived yet. However, each of your friends has told you their list of answers and their total score. You also remember your own list of answers. You are an optimist and you think that you probably did well!

Given that there is one correct list of answers (but you do not know what those answers are), and given your friends' answers and scores, what is the highest score that you possibly could have achieved?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each begins with one line with two integers $N$ and $Q$. Then, $N+1$ lines follow. The $i$-th of these lines represents the $i$-th examinee's list of answers $A_i$, which has $Q$ characters, each either T (True) or F (False). $A_{N+1}$ is your own list of answers. Finally, one line with $N$ integers follows. The $i$-th of these integers, $S_i$, is the $i$-th examinee's score. Your own score is not in this list, because it is unknown.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the highest score that you could have achieved that is consistent with the given information.

• $1 \le T \le 100$.
• The length of $A_i$ is $Q$, for all $i$.
• Each character of $A_i$ is either T or F, for all $i$.
• $0 \le S_i \le Q$.
• It is guaranteed that at least one list of correct answers is consistent with all of the friends' answers and scores.

Note that the last sample case would not appear in the Small dataset.

In sample case #1, your friend answered TF and you answered FF, and exactly one of your friend's answers was right. If your friend was wrong on question 1 and right on question 2, then the real set of answers is FF and you got both questions right. It is impossible to do better than this!

In sample case #2, your friend answered all Ts and got all of the questions wrong, so the real set of answers must be all Fs, which means that you got only question 3 right.

In sample case #3, the only possible real lists of answers that are consistent with the given information are FTT and FFF. For example, the real answer list cannot be TFT, because the first friend's answers and score would be consistent with that, but the second friend would have scored 0 instead of 2. Of these two possibilities, FTT is more favorable to you and would give you a score of 2.