{"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":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003eBerland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem.\u003c/p\u003e\n\u003cp\u003eThough there are lots and lots of victories in history of Berland, there is the one that stand out the most. King wants to mention it in the anthem as many times as possible.\u003c/p\u003e\n\u003cp\u003eHe has already composed major part of the anthem and now just needs to fill in some letters. King asked you to help him with this work.\u003c/p\u003e\n\u003cp\u003eThe anthem is the string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e of no more than \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e small Latin letters and question marks. The most glorious victory is the string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e of no more than \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e small Latin letters. You should replace all the question marks with small Latin letters in such a way that the number of occurrences of string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e in string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e is maximal.\u003c/p\u003e\n\u003cp\u003eNote that the occurrences of string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e can overlap. Check the third example for clarification.\u003c/p\u003e\n 给定一个字符串s,和一个字符串t,t只包含小写字母,s包含小写字母和通配符\u0027?\u0027。询问t可能在s中最多出现多少次,t出现的位置可以相互覆盖。"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains string of small Latin letters and question marks \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ |\u003ci\u003es\u003c/i\u003e| ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e\n\u003cp\u003eThe second line contains string of small Latin letters \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ |\u003ci\u003et\u003c/i\u003e| ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e\n\u003cb\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eProduct of lengths of strings \u003cspan class\u003d\"tex-span\"\u003e|\u003ci\u003es\u003c/i\u003e|·|\u003ci\u003et\u003c/i\u003e|\u003c/span\u003e won\u0027t exceed \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e7\u003c/sup\u003e\u003c/span\u003e.\u003c/span\u003e\u003c/p\u003e\u003c/b\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput the maximum number of occurrences of string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e you can achieve by replacing all the question marks in string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e with small Latin letters.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003ewinlose???winl???w??\u003cbr\u003ewin\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e5\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003eglo?yto?e??an?\u003cbr\u003eor\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e3\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e??c?????\u003cbr\u003eabcab\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e2\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example the resulting string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e is \u003cspan class\u003d\"tex-font-style-tt\"\u003e\"winlose\u003cspan class\u003d\"tex-font-style-bf\"\u003ewin\u003c/span\u003ewinl\u003cspan class\u003d\"tex-font-style-bf\"\u003ewin\u003c/span\u003ew\u003cspan class\u003d\"tex-font-style-bf\"\u003ein\u003c/span\u003e\"\u003c/span\u003e\u003c/p\u003e\n\u003cp\u003eIn the second example the resulting string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e is \u003cspan class\u003d\"tex-font-style-tt\"\u003e\"glo\u003cspan class\u003d\"tex-font-style-bf\"\u003er\u003c/span\u003eyto\u003cspan class\u003d\"tex-font-style-bf\"\u003er\u003c/span\u003ee\u003cspan class\u003d\"tex-font-style-bf\"\u003eor\u003c/span\u003ean\u003cspan class\u003d\"tex-font-style-bf\"\u003ed\u003c/span\u003e\"\u003c/span\u003e. The last letter of the string can be arbitrary.\u003c/p\u003e\n\u003cp\u003eIn the third example occurrences of string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e are overlapping. String \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e with maximal number of occurrences of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e is \u003cspan class\u003d\"tex-font-style-tt\"\u003e\"\u003cspan class\u003d\"tex-font-style-bf\"\u003eab\u003c/span\u003ec\u003cspan class\u003d\"tex-font-style-bf\"\u003eabcab\u003c/span\u003e\"\u003c/span\u003e.\u003c/p\u003e"}}]}