영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Points | Constraints |
|---|---|---|
| 1 | 9 | K = 2, N ≤ 4, M ≤ 100 |
| 2 | 9 | K ≤ 6, N ≤ 5, M ≤ 100 |
| 3 | 12 | K ≤ 20, N ≤ 6, M ≤ 1000 |
| 4 | 14 | K ≤ 15, N ≤ 6, M ≤ 10000 |
| 5 | 21 | K ≤ 20, N ≤ 6, M ≤ 100000 |
| 6 | 35 | K ≤ 10, N ≤ 13, M ≤ 500 |
예제
예제 1
4 3 5 TSU NKT KMO LJA KATT NATT STOL MASK KOST
3