마법적 사고 v2

당신과 친구 $N$명은 마법학교에 들어가려고 B.A.T.(Binary Answer Test)를 방금 치렀습니다. B.A.T.에는 참거짓 문항 $Q$개가 있고, 각 문항은 1점입니다. 당신에게는 마법 능력이 없어서 아무 답이나 골라 잘 되기를 바랐습니다.

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

정답 목록은 하나로 정해져 있지만 그 내용은 알 수 없습니다. 친구들의 답안과 점수가 주어졌을 때, 당신이 얻을 수 있었던 최고 점수는 얼마입니까?

입력의 첫 줄에 테스트 케이스 수 $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 \le T \le 100$.
• 모든 $i$에 대해 $A_i$의 길이는 $Q$입니다.
• 모든 $i$에 대해 $A_i$의 각 문자는 T 또는 F입니다.
• $0 \le S_i \le Q$.
• 친구들의 답안과 점수 전부와 모순되지 않는 정답 목록이 적어도 하나 있다고 보장됩니다.

데이터셋이 Small인 경우 마지막 예시 케이스는 나오지 않습니다.

예시 케이스 #1에서 친구는 TF, 당신은 FF로 답했고, 친구의 답 중 정확히 하나가 맞았습니다. 친구가 1번 문항을 틀리고 2번 문항을 맞혔다면 실제 정답은 FF이고 당신은 두 문항을 모두 맞힌 것입니다. 이보다 나은 결과는 불가능합니다.

예시 케이스 #2에서 친구는 모두 T로 답했고 전부 틀렸습니다. 따라서 실제 정답은 모두 F여야 하며, 당신이 맞힌 문항은 3번뿐입니다.

예시 케이스 #3에서 주어진 정보와 모순되지 않는 실제 답안 목록은 FTT와 FFF뿐입니다. 예를 들어 실제 답안이 TFT일 수는 없습니다. 첫 번째 친구의 답안과 점수는 그것과 맞지만, 두 번째 친구의 점수가 2점이 아니라 0점이 되기 때문입니다. 이 두 가능성 중 FTT가 당신에게 더 유리하며, 그 경우 당신은 2점을 얻습니다.