마법 같은 생각 v2

당신과 친구 N명은 마법 학교에 들어가기 위해 방금 B.A.T(이진 답변 시험)을 치렀다. B.A.T에는 Q개의 참·거짓 문제가 있으며, 각 문제는 1점이다. 당신에게는 마법의 힘이 없으므로, 그저 임의로 답을 고르고 좋은 결과가 나오기를 바랐다.

시험 결과는 이미 메추라기 우편으로 발송되었지만, 당신의 결과를 운반하는 메추라기는 아직 도착하지 않았다. 하지만 각 친구는 자신의 답 목록과 총점을 당신에게 알려 주었다. 당신은 자신의 답 목록도 기억하고 있다. 당신은 낙관주의자라서 아마 시험을 잘 봤을 것이라고 생각한다!

정답 목록이 하나 존재하지만 그 답이 무엇인지는 알지 못하고, 친구들의 답과 점수가 주어질 때, 당신이 얻었을 가능성이 있는 최고 점수는 얼마인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 모든 i에 대해 $A_{i}$의 길이는 Q이다. 모든 i에 대해 $A_{i}$의 각 문자는 T 또는 F이다. 0 ≤ $S_{i}$ ≤ Q. 모든 친구의 답과 점수에 부합하는 가능한 정답 목록이 적어도 하나 존재함이 보장된다.

작은 데이터 세트(테스트 세트 1 - 공개)

N = 1. 1 ≤ Q ≤ 10.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 2. 1 ≤ Q ≤ 50.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 Q가 있는 한 줄로 시작한다. 그다음 N+1개의 줄이 주어진다. 이 줄들 중 i번째 줄은 i번째 응시자의 답 목록 $A_{i}$을 나타내며, Q개의 문자로 이루어져 있고 각 문자는 T 또는 F(참 또는 거짓을 나타냄)이다. $A_{N+1}$은 당신 자신의 답 목록이다. 마지막으로 N개의 정수가 있는 한 줄이 주어진다. 이 정수들 중 i번째 정수 $S_{i}$는 i번째 응시자의 점수를 나타낸다. (당신의 점수는 알 수 없으므로 이 목록에 포함되지 않는다는 점에 유의하라.)

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 주어진 정보에 부합하면서 당신이 얻었을 가능성이 있는 최고 점수이다.

마지막 예제 케이스는 작은 데이터 세트에 나타나지 않는다는 점에 유의하라.

예제 케이스 #1에서 친구는 TF이라고 답했고 당신은 FF이라고 답했으며, 친구의 답 중 정확히 하나가 맞았다. 친구가 문제 1에서 틀리고 문제 2에서 맞았다면, 실제 정답 목록은 FF이고 당신은 두 문제를 모두 맞혔다. 이보다 더 잘하는 것은 불가능하다!

예제 케이스 #2에서 친구는 모두 T로 답했고 모든 문제를 틀렸으므로, 실제 정답 목록은 모두 F여야 한다. 이는 당신이 문제 3만 맞혔다는 뜻이다.

예제 케이스 #3에서 주어진 정보에 부합하는 가능한 실제 정답 목록은 FTT과 FFF뿐이다. (예를 들어 실제 정답 목록은 TFT일 수 없다. 첫 번째 친구의 답과 점수는 이에 부합하지만, 두 번째 친구는 2이 아니라 0점을 받았을 것이기 때문이다.) 이 두 가능성 중 FTT이 당신에게 더 유리하며, 당신에게 2점을 줄 것이다.