가장 재미있는 단어 찾기

다음 주는 Siv의 생일이고 Cel은 그녀를 위한 생일 선물을 준비하고 있다. Siv이 퍼즐을 좋아하기 때문에 Cel은 선물로 단어 찾기 퍼즐을 만들고 있다.

단어 찾기 퍼즐에서는 풀이하는 사람에게 R개의 행과 C개의 열로 이루어진 직사각형 격자가 주어지며, 격자 안에 숨겨진 유효한 단어를 모두 찾아야 한다. 숨겨진 각 단어는 격자에서 가로 또는 세로로 나타날 수 있지만 대각선으로는 NOT 나타날 수 있으며, 정방향이나 역방향일 수 있다. 숨겨진 단어들은 서로 겹칠 수 있다.

Cel에게는 W개의 서로 다른 단어가 들어 있는 사전이 있으며, 이 단어들만 퍼즐 격자 안에 숨겨질 수 있다. (물론 격자의 모든 연속한 가로 또는 세로 부분에 숨겨진 단어 중 하나가 반드시 포함되는 것은 아니다.) 이 단어들이 반드시 실제 영어 단어인 것은 아니다. 각 단어는 격자에 한 번 이상 나타날 수도 있고, 전혀 나타나지 않을 수도 있다.

Cel은 이미 단어 찾기 퍼즐을 만들었다. 하지만 문제가 하나 있다. 퍼즐이 너무 커서 종이 한 장에 인쇄할 수 없다. Siv의 생일이 곧 다가오므로 새로운 단어 찾기 퍼즐을 처음부터 만들 시간은 충분하지 않다. So Cel은 원래 격자에서 비어 있지 않고 격자 선에 맞는 부분 격자를 선택하기만 해서 격자의 크기를 줄일 수 있을지 궁금해한다.

부분 격자를 무작위로 선택하면 숨겨진 단어가 많지 않은 지루한 퍼즐이 될 수도 있다. So Cel은 재미 값이 가장 큰 부분 격자를 선택하려 하며, 부분 격자의 재미 값은 다음과 같이 정의된다.

재미 값 = (일치한 단어들의 전체 길이) / ((부분 격자의 너비) + (부분 격자의 높이))

참고:

• 단어로 집계되려면 단어 전체가 부분 격자에 나타나야 한다.

• 어떤 단어가 부분 격자에 x번 나타나면, 위 식에서 그 단어의 길이를 x번 더해야 한다.

• 어떤 단어와 그 단어를 뒤집은 것이 모두 부분 격자에 나타나면 같은 위치에 나타나더라도 두 출현을 모두 센다.

• 재미 값이 가장 큰 부분 격자는 원래 격자 전체일 수도 있다.

Cel이 부분 격자가 가질 수 있는 가장 큰 재미 값과 이 재미 값을 갖는 서로 다른 부분 격자의 수를 구하도록 도와주자. 두 부분 격자는 격자의 어떤 칸, 즉 어떤 (행, 열) 위치가 한 부분 격자에는 포함되지만 다른 부분 격자에는 포함되지 않을 때, 그리고 그럴 때에만 서로 다른 것으로 간주한다.

제한

• 1 ≤ T ≤ 100.

• 테스트 세트당 시간 제한: 240초.

• 메모리 제한: 1 GB.

• 1 ≤ R ≤ 100.

• 1 ≤ C ≤ 100.

• 유효한 단어 목록에는 같은 단어가 두 번 이상 나타나지 않는다.

• 유효한 단어 목록에 있는 모든 단어의 길이를 합하면 최대 5000글자이다.

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

• 각 유효한 단어의 길이는 정확히 1이다.

• 1 ≤ W ≤ 26.

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

• 1 ≤ W ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫 번째 줄에는 위에서 설명한 3개의 정수 R, C, W가 주어진다.

• 다음 R개의 각 줄에는 정확히 C개의 영문 대문자가 주어진다.

• 다음 W개의 각 줄에는 정확히 하나의 유효한 단어가 주어진다. 각 단어는 영문 대문자로만 이루어진다.

각 테스트 케이스마다 Case #x: y/z n을 포함하는 한 줄을 출력한다. 여기서:

• x은 1부터 시작하는 테스트 케이스 번호이다.

• y/z은 부분 격자가 가질 수 있는 가장 큰 재미 값과 같은 기약분수이다(위에서 설명한 바와 같다).

• y은 음이 아닌 정수이다.

• z은 양의 정수이다.

• n은 재미 값이 y/z과 같은 부분 격자의 수이다.

y와 z의 최대공약수가 1일 때 y/z을 기약분수라고 한다.

(i, j)는 i번째 행과 j번째 열에 있는 칸을 나타낸다고 하자.

예제 케이스 #1에서 재미 값이 가장 높은 부분 격자는 격자 전체이다. 유효한 단어 A은 격자에 8번 나타난다.

• (1, 1) 칸에서 가로로 2번 나타난다(정방향으로 한 번, 역방향으로 한 번).

• (1, 1) 칸에서 세로로 2번 나타난다(정방향으로 한 번, 역방향으로 한 번).

• (1, 2) 칸에서 4번 나타난다(가로와 세로, 정방향과 역방향).

예제 케이스 #2에는 재미 값이 0과 같은 부분 격자가 3개 있다.

• (1, 1) 칸 하나로만 이루어진 부분 격자.

• (1, 2) 칸 하나로만 이루어진 부분 격자.

• 왼쪽 위 모서리가 (1, 1) 칸이고 오른쪽 아래 모서리가 (1, 2) 칸인 부분 격자.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서 재미 값이 가장 높은 부분 격자는 격자 전체이다. 유효한 단어 ABC은 (1, 1) 칸부터 가로로 나타나고, 유효한 단어 CBA은 (1, 1) 칸부터 역방향으로 가로로 나타난다. 따라서 격자 전체의 재미 값은 6/(1 + 3) = 3/2과 같다.

예제 케이스 #2에서 재미 값이 가장 높은 부분 격자의 왼쪽 위 모서리는 (1, 1) 칸이고 오른쪽 아래 모서리는 (3, 3) 칸이다. 유효한 단어 AA은 부분 격자에 24번 나타난다.

• 가로로 12번 나타난다(정방향으로 6번, 역방향으로 6번).

• 세로로 12번 나타난다(정방향으로 6번, 역방향으로 6번).

참고: 이 문제에는 인터프리터 방식의 언어나 느린 언어를 사용하지 않는 것을 권장한다.