{"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":"\u003cp\u003eJunes is going to set up for a contest, and now he has written a statement for an easy problem. The statement is a string of length $$$n$$$ consisting of lowercase Latin latters. Vasya thinks that the statement can be considered hard if it contains a subsequence \u003cspan class\u003d\"tex-font-style-tt\"\u003ehard\u003c/span\u003e; otherwise the statement is easy. For example, \u003cspan class\u003d\"tex-font-style-tt\"\u003ehard\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003ehzazrzd\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003ehaaaaard\u003c/span\u003e can be considered hard statements, while \u003cspan class\u003d\"tex-font-style-tt\"\u003ehar\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003ehart\u003c/span\u003e and \u003cspan class\u003d\"tex-font-style-tt\"\u003edrah\u003c/span\u003e are easy statements. \u003c/p\u003e\u003cp\u003eVasya doesn\u0027t want the statement to be hard. He may remove some characters from the statement in order to make it easy. But, of course, some parts of the statement can be crucial to understanding. Initially the \u003cspan class\u003d\"tex-font-style-it\"\u003eambiguity\u003c/span\u003e of the statement is $$$0$$$, and removing $$$i$$$-th character increases the \u003cspan class\u003d\"tex-font-style-it\"\u003eambiguity\u003c/span\u003e by $$$a_i$$$ (the index of each character is considered as it was in the original statement, so, for example, if you delete character \u003cspan class\u003d\"tex-font-style-tt\"\u003er\u003c/span\u003e from \u003cspan class\u003d\"tex-font-style-tt\"\u003ehard\u003c/span\u003e, and then character \u003cspan class\u003d\"tex-font-style-tt\"\u003ed\u003c/span\u003e, the index of \u003cspan class\u003d\"tex-font-style-tt\"\u003ed\u003c/span\u003e is still $$$4$$$ even though you delete it from the string \u003cspan class\u003d\"tex-font-style-tt\"\u003ehad\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eVasya wants to calculate the minimum \u003cspan class\u003d\"tex-font-style-it\"\u003eambiguity\u003c/span\u003e of the statement, if he removes some characters (possibly zero) so that the statement is easy. Help him to do it!\u003c/p\u003e\u003cp\u003eRecall that subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer $$$n$$$ ($$$1 \\le n \\le 10^5$$$) — the length of the statement.\u003c/p\u003e\u003cp\u003eThe second line contains one string $$$s$$$ of length $$$n$$$, consisting of lowercase Latin letters — the statement written by Vasya.\u003c/p\u003e\u003cp\u003eThe third line contains $$$n$$$ integers $$$a_1, a_2, \\dots, a_n$$$ ($$$1 \\le a_i \\le 998244353$$$).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint minimum possible \u003cspan class\u003d\"tex-font-style-it\"\u003eambiguity\u003c/span\u003e of the statement after Vasya deletes some (possibly zero) characters so the resulting statement is easy.\u003c/p\u003e"}},{"title":"Sample 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\u003e6\nhhardh\n3 2 9 11 7 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 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\u003e8\nhhzarwde\n3 2 6 9 4 8 7 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 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\u003e6\nhhaarr\n1 2 3 4 5 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example, first two characters are removed so the result is \u003cspan class\u003d\"tex-font-style-tt\"\u003eardh\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second example, $$$5$$$-th character is removed so the result is \u003cspan class\u003d\"tex-font-style-tt\"\u003ehhzawde\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the third example there\u0027s no need to remove anything.\u003c/p\u003e"}}]}