{"raw_statement":[{"iden":"statement","content":"Vasya learns to type. He has an unusual keyboard at his disposal: it is rectangular and it has _n_ rows of keys containing _m_ keys in each row. Besides, the keys are of two types. Some of the keys have lowercase Latin letters on them and some of the keys work like the \"Shift\" key on standard keyboards, that is, they make lowercase letters uppercase.\n\nVasya can press one or two keys with one hand. However, he can only press two keys if the Euclidean distance between the centers of the keys does not exceed _x_. The keys are considered as squares with a side equal to 1. There are no empty spaces between neighbouring keys.\n\nVasya is a very lazy boy, that's why he tries to type with one hand as he eats chips with his other one. However, it is possible that some symbol can't be typed with one hand only, because the distance between it and the closest \"Shift\" key is strictly larger than _x_. In this case he will have to use his other hand. Having typed the symbol, Vasya returns other hand back to the chips.\n\nYou are given Vasya's keyboard and the text. Count the minimum number of times Vasya will have to use the other hand."},{"iden":"input","content":"The first line contains three integers _n_, _m_, _x_ (1 ≤ _n_, _m_ ≤ 30, 1 ≤ _x_ ≤ 50).\n\nNext _n_ lines contain descriptions of all the keyboard keys. Each line contains the descriptions of exactly _m_ keys, without spaces. The letter keys are marked with the corresponding lowercase letters. The \"Shift\" keys are marked with the \"_S_\" symbol.\n\nThen follow the length of the text _q_ (1 ≤ _q_ ≤ 5·105). The last line contains the text _T_, which consists of _q_ symbols, which are uppercase and lowercase Latin letters."},{"iden":"output","content":"If Vasya can type the text, then print the minimum number of times he will have to use his other hand. Otherwise, print \"-1\" (without the quotes)."},{"iden":"examples","content":"Input\n\n2 2 1\nab\ncd\n1\nA\n\nOutput\n\n\\-1\n\nInput\n\n2 2 1\nab\ncd\n1\ne\n\nOutput\n\n\\-1\n\nInput\n\n2 2 1\nab\ncS\n5\nabcBA\n\nOutput\n\n1\n\nInput\n\n3 9 4\nqwertyuio\nasdfghjkl\nSzxcvbnmS\n35\nTheQuIcKbRoWnFOXjummsovertHeLazYDOG\n\nOutput\n\n2"},{"iden":"note","content":"In the first sample the symbol \"_A_\" is impossible to print as there's no \"Shift\" key on the keyboard.\n\nIn the second sample the symbol \"_e_\" is impossible to print as there's no such key on the keyboard.\n\nIn the fourth sample the symbols \"_T_\", \"_G_\" are impossible to print with one hand. The other letters that are on the keyboard can be printed. Those symbols come up in the text twice, thus, the answer is 2."}],"translated_statement":[{"iden":"statement","content":"Vasya 正在学习打字。他有一副不寻常的键盘：它是矩形的，有 #cf_span[n] 行按键，每行包含 #cf_span[m] 个按键。此外，按键分为两种类型：一些按键上标有小写拉丁字母，另一些按键的功能类似于标准键盘上的 \"Shift\" 键，即它们能将小写字母变为大写。\n\nVasya 可以用一只手按下其中一个或两个按键。但他只能在两个按键中心之间的欧几里得距离不超过 #cf_span[x] 时，才可以用一只手同时按下两个按键。按键被视为边长为 1 的正方形，相邻按键之间没有空隙。\n\nVasya 是个非常懒惰的男孩，因此他一边用另一只手吃薯片，一边尽量只用一只手打字。然而，某些字符可能无法仅用一只手输入，因为该字符对应的按键与最近的 \"Shift\" 键之间的距离严格大于 #cf_span[x]。在这种情况下，他必须使用另一只手。输入完该字符后，Vasya 会将另一只手放回薯片上。\n\n给定 Vasya 的键盘和一段文本，请计算 Vasya 必须使用另一只手的最少次数。\n\n第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[x]（#cf_span[1 ≤ n, m ≤ 30, 1 ≤ x ≤ 50]）。\n\n接下来 #cf_span[n] 行描述键盘上所有按键。每行包含恰好 #cf_span[m] 个按键的描述，无空格。字母键用对应的小写字母标记，\"Shift\" 键用 \"_S_\" 标记。\n\n随后是文本长度 #cf_span[q] #cf_span[(1 ≤ q ≤ 5·105)]。最后一行包含由 #cf_span[q] 个符号组成的文本 #cf_span[T]，这些符号为大写和小写拉丁字母。\n\n如果 Vasya 能够输入该文本，则输出他必须使用另一只手的最少次数；否则，输出 \"-1\"（不含引号）。\n\n在第一个样例中，符号 \"_A_\" 无法输入，因为键盘上没有 \"Shift\" 键。\n\n在第二个样例中，符号 \"_e_\" 无法输入，因为键盘上没有该键。\n\n在第四个样例中，符号 \"_T_\" 和 \"_G_\" 无法仅用一只手输入。键盘上其他字母可以输入。这些符号在文本中各出现一次，因此答案为 2。"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[x]（#cf_span[1 ≤ n, m ≤ 30, 1 ≤ x ≤ 50]）。接下来 #cf_span[n] 行描述键盘上所有按键。每行包含恰好 #cf_span[m] 个按键的描述，无空格。字母键用对应的小写字母标记，\"Shift\" 键用 \"_S_\" 标记。随后是文本长度 #cf_span[q] #cf_span[(1 ≤ q ≤ 5·105)]。最后一行包含由 #cf_span[q] 个符号组成的文本 #cf_span[T]，这些符号为大写和小写拉丁字母。"},{"iden":"output","content":"如果 Vasya 能够输入该文本，则输出他必须使用另一只手的最少次数；否则，输出 \"-1\"（不含引号）。"},{"iden":"examples","content":"输入\n2 2 1\nabcd\n1\nA\n输出\n-1\n\n输入\n2 2 1\nabcd\n1\ne\n输出\n-1\n\n输入\n2 2 1\nabcS\n5\nabcBA\n输出\n1\n\n输入\n3 9 4\nqwertyuio\nasdfghjkl\nSzxcvbnmS\n35\nTheQuIcKbRoWnFOXjummsovertHeLazYDOG\n输出\n2"},{"iden":"note","content":"在第一个样例中，符号 \"_A_\" 无法输入，因为键盘上没有 \"Shift\" 键。在第二个样例中，符号 \"_e_\" 无法输入，因为键盘上没有该键。在第四个样例中，符号 \"_T_\" 和 \"_G_\" 无法仅用一只手输入。键盘上其他字母可以输入。这些符号在文本中各出现一次，因此答案为 2。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ n, m, x \\in \\mathbb{N} $: dimensions of the keyboard ($ n $ rows, $ m $ columns), and maximum allowed Euclidean distance for two-key press with one hand.\n- Let $ K \\in (\\Sigma \\cup \\{\\texttt{S}\\})^{n \\times m} $: a grid representing the keyboard, where:\n  - $ \\Sigma = \\{a, b, \\dots, z\\} $: set of lowercase letters.\n  - $ \\texttt{S} $: denotes a Shift key.\n- Let $ T \\in (\\Sigma \\cup \\Sigma^{\\text{upper}})^q $: target text of length $ q $, where $ \\Sigma^{\\text{upper}} = \\{A, B, \\dots, Z\\} $: uppercase letters.\n\n**Given:**\n\n- Each key is a unit square; positions are indexed by $ (i, j) $, $ 0 \\le i < n $, $ 0 \\le j < m $.\n- Euclidean distance between centers of keys at $ (i_1, j_1) $ and $ (i_2, j_2) $ is $ \\sqrt{(i_1 - i_2)^2 + (j_1 - j_2)^2} $.\n- Vasya can press:\n  - One key (for lowercase letters or Shift).\n  - Two keys simultaneously **iff** their Euclidean distance $ \\le x $ (one hand).\n- To type an **uppercase letter** $ L $, Vasya must press the corresponding lowercase letter $ l $ and a Shift key **together** (if possible with one hand), or use two hands (Shift with other hand, letter with dominant hand).\n\n**Constraints:**\n\n- A lowercase letter $ l $ is available on the keyboard if $ \\exists (i, j) $ such that $ K[i][j] = l $.\n- A Shift key is available if $ \\exists (i, j) $ such that $ K[i][j] = \\texttt{S} $.\n- For an uppercase letter $ L $, let $ l = \\text{lower}(L) $. Then:\n  - If $ l $ is not on the keyboard → impossible.\n  - Else, let $ S = \\{ (i, j) \\mid K[i][j] = \\texttt{S} \\} $: set of Shift key positions.\n  - Let $ P = \\{ (i, j) \\mid K[i][j] = l \\} $: set of positions of $ l $.\n  - Define $ d_{\\min}(L) = \\min_{p \\in P, s \\in S} \\text{dist}(p, s) $.\n  - If $ d_{\\min}(L) > x $, then $ L $ **cannot** be typed with one hand.\n\n**Objective:**\n\nCount the number of characters in $ T $ that are uppercase letters $ L $ such that:\n- $ \\text{lower}(L) $ exists on the keyboard, **and**\n- $ d_{\\min}(L) > x $.\n\nIf any character in $ T $ is:\n- An uppercase letter $ L $ such that $ \\text{lower}(L) $ does **not** exist on the keyboard, **or**\n- A lowercase letter not present on the keyboard,\n\nthen output $ -1 $.\n\nOtherwise, output the count of uppercase letters in $ T $ that require two hands (i.e., $ d_{\\min}(L) > x $).\n\n---\n\n**Formal Output:**\n\nLet $ \\mathcal{L} = \\{ \\text{lower}(c) \\mid c \\in T \\} $.\n\n1. If $ \\exists c \\in T $ such that:\n   - $ c \\in \\Sigma $ and $ \\nexists (i,j) $ with $ K[i][j] = c $, **or**\n   - $ c \\in \\Sigma^{\\text{upper}} $ and $ \\nexists (i,j) $ with $ K[i][j] = \\text{lower}(c) $,\n   then output $ -1 $.\n\n2. Else:\n   - Let $ S = \\{ (i,j) \\mid K[i][j] = \\texttt{S} \\} $.\n   - For each uppercase letter $ L \\in T $, let $ l = \\text{lower}(L) $, and let $ P_l = \\{ (i,j) \\mid K[i][j] = l \\} $.\n   - Compute $ d_L = \\min_{p \\in P_l, s \\in S} \\sqrt{(i_p - i_s)^2 + (j_p - j_s)^2} $.\n   - Count $ \\#\\{ L \\in T \\mid L \\in \\Sigma^{\\text{upper}} \\text{ and } d_L > x \\} $.\n\nOutput this count.","simple_statement":null,"has_page_source":false}