밀크티
시간 제한30초메모리 제한1024 MB
길이 P인 N개의 이진 선호 문자열과 M개의 금지된 문자열이 주어질 때, 모든 선호와의 해밍 거리 합이 최소가 되는 허용된 문자열을 고른다.
문제
중국의 밀크티는 아주 맛있다. 밀크티 주문을 고를 때는 "얼음 넣음"/"얼음 뺌", "설탕 넣음"/"설탕 뺌", "버블 넣음"/"버블 뺌", "푸딩 넣음"/"푸딩 뺌"처럼 두 가지 중 하나를 고르는 옵션이 많다. 손님의 밀크티 취향은 이진 문자열로 나타낼 수 있다. 예를 들어 위의 네 옵션을 주어진 순서대로 사용하면, 문자열 1100은 "얼음 넣음, 설탕 넣음, 버블 뺌, 푸딩 뺌"을 뜻한다.
오늘 Shakti는 N명의 친구에게 밀크티를 하나씩 사 주는 당번이며, 가게에서는 P개의 이진 옵션을 제공한다. 그런데 모두의 취향을 모아 보니 주문이 너무 복잡해져서, Shakti는 모두에게 같은 종류의 밀크티를 사기로 했다. Shakti는 친구마다 만족하지 못한 취향 하나당 한 번씩 불평한다는 것을 알고 있다. 예를 들어 두 친구의 취향이 101과 010이고 Shakti가 001을 고르면, 첫 번째 친구는 한 번, 두 번째 친구는 두 번 불평해서 총 세 번의 불평이 나온다.
또한 가게가 만들지 않는 M개의 금지된 밀크티 종류가 있어서, Shakti는 그중 어떤 것도 고를 수 없다.
Shakti가 받을 수 있는 불평 횟수의 최솟값은 얼마인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 따른다. 각 테스트 케이스의 첫 줄에는 위에서 설명한 세 정수 N, M, P가 주어진다. 그다음 N개의 줄에는 이진 문자열이 하나씩 주어지며, 이는 N명의 친구의 취향을 나타낸다. 마지막으로 M개의 줄에는 이진 문자열이 하나씩 주어지며, 이는 가게가 만들지 않는 금지된 밀크티 종류를 나타낸다. 이진 문자열은 0과 1 문자로만 이루어진다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 위 규칙에 따라 Shakti가 받을 수 있는 불평 횟수의 최솟값이다.
제한
- 1 ≤ T ≤ 100.
- 금지된 밀크티 종류는 모두 서로 다르다.
힌트
예제 1에는 친구가 3명 있고, 이들은 1100, 1010, 0000 종류의 밀크티를 원한다. Shakti가 1000을 고를 수 있다면 친구마다 한 번씩 불평해서 총 3번의 불평이 나온다. 하지만 1000은 가게에서 팔지 않는다. 따라서 이 제약 아래에서 최적해는 1100을 고르는 것이다. 그러면 친구들은 각각 0번, 2번, 2번 불평해서 총 4번의 불평이 나온다.
예제 2에서 Shakti의 최선의 선택은 1110을 고르는 것이다. 친구마다 한 번씩 불평해서 총 2번의 불평이 나온다. 서로 다른 친구가 같은 취향을 가질 수 있다는 점에 유의하자. 또한 Small과 Large 데이터셋의 제한은 금지되지 않은 밀크티 종류가 항상 하나 이상 존재함을 보장한다.