{"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\u003eVasya học cách gõ phím. Anh ấy có một bàn phím không bình thường: nó hình chữ nhật và có \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e hàng phím chứa \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e phím trong mỗi hàng. Ngoài ra, các phím thuộc hai loại. Một số phím có chữ cái Latin thường và một số phím hoạt động giống như phím \"Shift\" trên bàn phím tiêu chuẩn, nghĩa là chúng biến chữ cái thường thành chữ cái in hoa.\u003c/p\u003e\u003cp\u003eVasya có thể nhấn một hoặc hai phím bằng một tay. Tuy nhiên, anh ấy chỉ có thể nhấn hai phím nếu khoảng cách Euclid giữa trung tâm của các phím không vượt quá \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e. Các phím được coi như hình vuông có cạnh bằng 1. Không có khoảng trống giữa các phím kề nhau.\u003c/p\u003e\u003cp\u003eVasya là một cậu bé rất lười biếng, đó là lý do tại sao anh ấy cố gắng gõ với một tay trong khi anh ấy ăn khoai tây chiên bằng tay còn lại. Tuy nhiên, có thể có một số ký hiệu không thể gõ bằng một tay duy nhất, vì khoảng cách giữa nó và phím \"Shift\" gần nhất lớn hơn \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e. Trong trường hợp này, anh ấy sẽ phải sử dụng tay còn lại. Sau khi gõ ký hiệu, Vasya trả tay còn lại về khoai tây.\u003c/p\u003e\u003cp\u003eBạn được cho bàn phím của Vasya và văn bản. Đếm số lần tối thiểu Vasya sẽ phải sử dụng tay còn lại.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa ba số nguyên \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\u003eTiếp theo \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e dòng 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 chính xác \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e 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 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eS\u003c/span\u003e\". \u003c/p\u003e\u003cp\u003eSau đó là độ dài của văn bản \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. Dòng cuối cùng chứa văn bản \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e, gồm \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e ký tự, là chữ cái Latin in hoa và thường.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eNếu Vasya có thể gõ văn bản, in ra số lần tối thiểu anh ấy sẽ phải sử dụng tay còn lại. Nếu không, in ra \"-1\" (không có dấu ngoặc).\u003c/p\u003e"}},{"title":"Ví dụ 1","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":"Ví dụ 2","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":"Ví dụ 3","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":"Ví dụ 4","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":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ 1, ký hiệu \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eA\u003c/span\u003e\" không thể gõ vì không có phím \"Shift\" trên bàn phím.\u003c/p\u003e\u003cp\u003eTrong ví dụ 2, ký hiệu \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ee\u003c/span\u003e\" không thể gõ vì không có phím đó trên bàn phím.\u003c/p\u003e\u003cp\u003eTrong ví dụ 4, các ký hiệu \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eT\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eG\u003c/span\u003e\" không thể gõ bằng một tay. Các chữ cái còn lại trên bàn phím có thể gõ. Những ký hiệu này xuất hiện trong văn bản hai lần, do đó, câu trả lời là 2.\u003c/p\u003e"}}]}