{"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Plagiarism has become one of the most common problems of contest programming. Immoral contest programmers often copy each other\u0027s code. To prevent this, contest platforms often deploy automated cheat detection systems that compare two person\u0027s code to check if they are the same or not. But those dishonest programmers even found a way to beat the system.\n\nConsider that, the original solution of a programming problem is **X**, a concatenation of **P** non-empty substrings **x\u003csub\u003e1\u003c/sub\u003ex\u003csub\u003e2\u003c/sub\u003e...x\u003csub\u003eP\u003c/sub\u003e**. Note that, each **x\u003csub\u003ei\u003c/sub\u003e** denotes a substring. Two rogue contest programmers, who copied from each other, will take this code, insert some arbitrary strings in between them, and submit it so that the automated system cannot detect their code.\n\nLet\u0027s say, the first contestant submitted the code **S** \u0026mdash; **s\u003csub\u003e1\u003c/sub\u003ex\u003csub\u003e1\u003c/sub\u003es\u003csub\u003e2\u003c/sub\u003ex\u003csub\u003e2\u003c/sub\u003e...s\u003csub\u003eP\u003c/sub\u003ex\u003csub\u003eP\u003c/sub\u003es\u003csub\u003eP+1\u003c/sub\u003e** where **s\u003csub\u003e1\u003c/sub\u003es\u003csub\u003e2\u003c/sub\u003e...s\u003csub\u003ep+1\u003c/sub\u003e** is a sequence of arbitrary strings. The second contestant submitted the code **T** \u0026mdash; **t\u003csub\u003e1\u003c/sub\u003ex\u003csub\u003e1\u003c/sub\u003et\u003csub\u003e2\u003c/sub\u003ex\u003csub\u003e2\u003c/sub\u003e...t\u003csub\u003eP\u003c/sub\u003ex\u003csub\u003eP\u003c/sub\u003et\u003csub\u003ep+1\u003c/sub\u003e** where **t\u003csub\u003e1\u003c/sub\u003et\u003csub\u003e2\u003c/sub\u003e...t\u003csub\u003ep+1\u003c/sub\u003e** is a sequence of arbitrary strings. Note that, each of the **s\u003csub\u003ei\u003c/sub\u003e**, and **t\u003csub\u003ei\u003c/sub\u003e** can consist of 0 or more characters.\n\nHowever, no matter what they insert in-between, the common portions remain the same. As a result, given two codes, we can easily find out whether they plagiarized or not. Now you will be presented with the two strings. Your task is to find the sum of the lengths of those **P** common substrings. If there are multiple possible answers, find the sum that is maximum."}},{"title":"Input","value":{"format":"MD","content":"Input starts with three space-separated integers **N**, **M**, and **P (1 \u0026leq; N, M \u0026leq; 10\u003csup\u003e3\u003c/sup\u003e, 1 \u0026leq; P \u0026leq; 10)** \u0026mdash; the length of **S**, the length of **T**, and the number of common substrings, respectively.\nThe following line contains a string **S** \u0026mdash; the code submitted by the first contestant.\nThe next line contains a string **T** \u0026mdash; the code submitted by the second contestant.\nBoth strings consist of lowercase English letters."}},{"title":"Output","value":{"format":"MD","content":"Print the sum of the lengths of the **P** common substrings.\nIt is guaranteed that at least one such subsequence exists."}},{"title":"Sample Input 1","value":{"format":"MD","content":"```\n9 12 4\nintforikk\nckintkkfodri\n```"}},{"title":"Sample Output 1","value":{"format":"MD","content":"```\n7\n```"}},{"title":"Sample Input 2","value":{"format":"MD","content":"```\n3 4 2\naeb\nabdc\n```"}},{"title":"Sample Output 2","value":{"format":"MD","content":"```\n2\n```"}},{"title":"Explanation","value":{"format":"MD","content":"For the first sample, we can consider **X** as `intfori`, which is common in both **S** and **T**.\nFor the second sample, we can consider **X** as `ab`, which is common in both **S** and **T**."}}]}