{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e瓦西娅正在学习打字。他有一个不寻常的键盘可供使用:它是矩形的,有 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 行键,每行包含 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e 个按键。此外,按键有两种类型。一些按键上有小写拉丁字母,而一些按键的功能类似于标准键盘上的“Shift”键,即可以将小写字母转换为大写字母。\u003c/p\u003e\u003cp\u003e瓦西娅可以用一只手按一个或两个按键。然而,他只能在按键中心之间的欧几里得距离不超过 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e 的情况下按下两个按键。按键被视为边长为1的正方形。相邻按键之间没有空隙。\u003c/p\u003e\u003cp\u003e瓦西娅是个非常懒惰的男孩,因此他试图用一只手打字,同时用另一只手吃薯片。然而,某些符号可能无法仅用一只手输入,因为它与最近的“Shift”键之间的距离严格大于 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e。在这种情况下,他将不得不使用另一只手。输入完符号后,瓦西娅将另一只手放回薯片上。\u003c/p\u003e\u003cp\u003e给定瓦西娅的键盘和文本。计算瓦西娅必须使用另一只手的最小次数。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含三个整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 30, 1 ≤ \u003ci\u003ex\u003c/i\u003e ≤ 50\u003c/span\u003e)。\u003c/p\u003e\u003cp\u003e接下来的 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 行包含所有键盘按键的描述。每行恰好包含 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e 个按键的描述,没有空格。字母按键用相应的小写字母标记。“Shift”键用 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eS\u003c/span\u003e\" 符号标记。\u003c/p\u003e\u003cp\u003e然后是文本的长度 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 5·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e)\u003c/span\u003e。最后一行包含文本 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e,由 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e 个符号组成,这些符号是大写和小写的拉丁字母。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e如果瓦西娅可以输入文本,则打印他必须使用另一只手的最小次数。否则,打印 \"-1\"(不带引号)。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 2 1\nab\ncd\n1\nA\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 2 1\nab\ncd\n1\ne\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 2 1\nab\ncS\n5\nabcBA\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 9 4\nqwertyuio\nasdfghjkl\nSzxcvbnmS\n35\nTheQuIcKbRoWnFOXjummsovertHeLazYDOG\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,符号 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eA\u003c/span\u003e\" 无法打印,因为键盘上没有“Shift”键。\u003c/p\u003e\u003cp\u003e在第二个示例中,符号 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ee\u003c/span\u003e\" 无法打印,因为键盘上没有这样的按键。\u003c/p\u003e\u003cp\u003e在第四个示例中,符号 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eT\u003c/span\u003e\"、\"\u003cspan class\u003d\"tex-font-style-tt\"\u003eG\u003c/span\u003e\" 无法用一只手打印。键盘上其他字母可以打印。这些符号在文本中出现了两次,因此答案是2。\u003c/p\u003e"}}]}