You and of your friends just took the B.A.T. (Binary Answer Test) to try to get into wizard school. The B.A.T. has true-false questions, and each one is worth 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?
Input Specification
The first line of the input gives the number of test cases, . test cases follow. Each begins with one line with two integers and . Then, lines follow; the of these lines represents the examinee's list of answers , and has characters, each of which is either T
or F
(representing True or False). is your own list of answers. Finally, one line with integers follows; the of these integers, , represents the examinee's score. (Note that your own score is not in this list, because it is unknown.)
Output Specification
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from ) and y
is the highest score that you possibly could have achieved that is consistent with the given information.
Limits
The length of is , for all .
Each character of is either T
or F
for all .
It is guaranteed that there is at least one possible list of correct answers that is consistent with all of the friends' answers and scores.
Subtask 1 [6/25]
Subtask 2 [19/25]
Sample Input
3
1 2
TF
FF
1
1 3
TTT
TTF
0
2 3
TTF
FTF
TTT
1 2
Sample Output
Case #1: 2
Case #2: 1
Case #3: 2
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 and right on question , 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 T
s and got all of the questions wrong, so the real set of answers must be all F
s, which means that you got only question 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
; the first friend's answers and score would be consistent with that, but the second friend would have scored instead of .) Of these two possibilities, FTT
is more favorable to you and would give you a score of .
Comments