루미 알고리즘

#1403플래티넘Bokstavstärningar

PO 2016 온라인 예선코딩출제 Pär Söderhjelm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Klara has N dices with letters written on them. Each die has a letter on each of its K sides. By throwing the dice and rearranging them in some arbitrary order, you can make construct a word with N letters.

Write a program to count the number of valid words that can be constructed using Klara's dice. You will get a wordlist, that contains all the M valid N-letter words.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: An illustration of the first example. Since K = 3, each die has three sides. You can also write STOL and MASK, but not NATT or KOST.

Input

The first line of input contains three space-separated integers N, K and M.

The next N lines each describe a die. Line i will contain K letters, the letters on the sides of the i:th die.

Finally, there will be M lines, the valid words. Each line will contain an N-letter word.

All words will only capital letters A-Z.

No letter will appear on more than one side of a die.

Output

Your program should print a single integer: the number of valid words that can be written.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
19K = 2, N ≤ 4, M ≤ 100
29K ≤ 6, N ≤ 5, M ≤ 100
312K ≤ 20, N ≤ 6, M ≤ 1000
414K ≤ 15, N ≤ 6, M ≤ 10000
521K ≤ 20, N ≤ 6, M ≤ 100000
635K ≤ 10, N ≤ 13, M ≤ 500

예제

예제 1

입력
4 3 5
TSU
NKT
KMO
LJA
KATT
NATT
STOL
MASK
KOST
출력
3

출처 표기

출처: Programmeringsolympiaden 2016년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.