{"trustable":false,"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":"MD","content":"Vasya đang học gõ bàn phím. Anh ấy có một chiếc bàn phím bản đặc biệt: nó hình chữ nhật và có $n$ hàng phím, mỗi hàng chứa $m$ phím. Ngoài ra, các phím được chia thành hai loại. Một số phím có chữ cái Latinh viết thường và một số phím hoạt động giống như phím \"Shift\" trên các bàn phím tiêu chuẩn, tức là, chúng biến chữ cái viết thường thành chữ cái viết hoa.\n\nVasya có thể nhấn một hoặc hai phím chỉ bằng một tay. Tuy nhiên, anh chỉ có thể nhấn hai phím nếu khoảng cách Euclide giữa tâm của hai phím không vượt quá $x$. Các phím được coi là các hình vuông có cạnh bằng 1. Không có khoảng trống nào giữa các phím liền kề.\n\nVasya là một cậu bé rất lười, vì vậy cậu ấy cố gắng gõ bằng một tay trong khi ăn Bim Bim bằng tay còn lại. Tuy nhiên, có thể một số ký tự không thể gõ được chỉ bằng một tay, bởi vì khoảng cách từ nó đến phím \"Shift\" gần nhất lớn hơn $x$. Trong trường hợp này, anh ấy sẽ phải sử dụng tay kia. Sau khi gõ xong ký tự, Vasya sẽ đưa tay kia trở lại với gói Bim Bim.\n\nBạn được cho bàn phím của Vasya và văn bản cậu ấy cần gõ. Hãy đếm số lần tối thiểu Vasya phải sử dụng tay ăn Bim Bim."}},{"title":"Dữ liệu","value":{"format":"MD","content":"- Dòng đầu tiên chứa ba số nguyên $n$, $m$, $x$ ($1 \\leq n, m \\leq 30$, $1 \\leq x \\leq 50$).\n- $n$ dòng tiếp theo chứa mô tả của tất cả các phím trên bàn phím. Mỗi dòng chứa mô tả của đúng $m$ phím, không có khoảng trắng. Các phím chữ cái được đánh dấu bằng các chữ cái thường tương ứng. Các phím \"Shift\" được đánh dấu bằng ký hiệu `S`.\n- Sau đó là độ dài của văn bản $q$ ($1 \\leq q \\leq 5 \\cdot 10^5$). \n- Dòng cuối cùng chứa văn bản $T$, bao gồm $q$ ký tự, là các chữ cái Latinh viết hoa và viết thường."}},{"title":"Kết quả","value":{"format":"MD","content":"Nếu Vasya có thể gõ đầy đủ văn bản, in ra số lần tối thiểu cậu ấy phải sử dụng cả hai tay để gõ phím. Ngược lại, in `-1`."}},{"title":"Ví dụ 1","value":{"format":"MD","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\n"}},{"title":"Ví dụ 2","value":{"format":"MD","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\n"}},{"title":"Ví dụ 3","value":{"format":"MD","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\n"}},{"title":"Ví dụ 4","value":{"format":"MD","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\n"}}]}