{"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\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\u003eYou are playing a game, and you are going to fight the secret boss. In this game, the boss doesn\u0027t attack you, but they can cast regeneration spells.\u003c/p\u003e\u003cp\u003eThe fight consists of exactly $$$N$$$ rounds, in each round the following actions can happen, in this order:\u003c/p\u003e\u003col\u003e\u003cli\u003e The boss can choose to cast the \"Regeneration\" spell.\u003c/li\u003e\u003cli\u003e You can choose to cast the \"Poison\" spell if you have any mana left.\u003c/li\u003e\u003cli\u003e You attack with a sword, dealing $$$X$$$ damage.\u003c/li\u003e\u003cli\u003e All the passive effects are applied.\u003c/li\u003e\u003c/ol\u003e\u003cp\u003eThere are two types of passive effects: regeneration and poison. The effects stack, which means that the current state of the boss can be described with three integers: current health points ($$$hp$$$), current poison stacks ($$$p$$$) and current regeneration stacks ($$$r$$$). At the beginning of the fight, there are no poison stacks and no regeneration stacks ($$$p\u003dr\u003d0$$$). Each poison stack deals $$$P$$$ damage, each regeneration stack heals $$$R$$$ health points.\u003c/p\u003e\u003cp\u003eSpells have the following effects:\u003c/p\u003e\u003cp\u003e\"Regeneration\": increase the number of regenerations stacks $$$r$$$ by $$$1$$$.\u003c/p\u003e\u003cp\u003e\"Poison\": increase the number of poison stacks $$$p$$$ by $$$1$$$. \u003cspan class\u003d\"tex-font-style-bf\"\u003eIf the number of regeneration stacks is strictly positive\u003c/span\u003e ($$$r \u0026gt; 0$$$), then decrease it by $$$1$$$.\u003c/p\u003e\u003cp\u003eAfter the round the $$$hp$$$ will decrease by $$$X + P \\cdot p - R \\cdot r$$$ (this value can be negative if the boss heals faster than you deal damage).\u003c/p\u003e\u003cp\u003eFor each round you know if the boss will cast \"Regeneration\". You have enough mana to cast \"Poison\" $$$K$$$ times (you don\u0027t have to use all of your mana). What\u0027s the largest total damage you can deal to the boss, in other words, what is the maximum value of $$$hp_{start} - hp_{end}$$$? Assume that $$$hp_{start} \u003d 10^{1000}$$$, so you can\u0027t actually kill the boss in $$$N$$$ rounds. Boss $$$hp$$$ can go higher than the initial value (see the third sample case).\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains $$$5$$$ integers $$$N$$$, $$$X$$$, $$$R$$$, $$$P$$$, $$$K$$$ ($$$1 \\le N, X, R, P \\le 10^6$$$, $$$0 \\le K \\le N$$$).\u003c/p\u003e\u003cp\u003eThe second line of the input contains a binary string of length $$$N$$$. The $$$i$$$-th character of this string is \u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e, if the boss casts \"Regeneration\" at the beginning of the $$$i$$$-th round, and \u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e otherwise.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput a single integer\u0026nbsp;— the largest total damage you can deal during the fight.\u003c/p\u003e"}},{"title":"Examples","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 1010 1 1 1\n01\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2021\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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 2 1 1 1\n001\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e10 1 10 40 1\n1111111111\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-40\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\u003eLet\u0027s look at the first sample. We can cast the \"Poison\" spell at most once. Let\u0027s look at what will happen if we cast this spell during the first round.\u003c/p\u003e\u003cul\u003e\u003cli\u003e During the first round, we apply a \"Poison\" spell, so at the end of this round there will be $$$0$$$ regeneration stacks, and $$$1$$$ poison stack. Therefore, the $$$hp$$$ will decrease by $$$X + P\\cdot 1 - R\\cdot 0 \u003d 1011$$$ this round.\u003c/li\u003e\u003cli\u003e At the beginning of the second round, the boss will cast the \"Regeneration\" spell, so there will be $$$1$$$ regeneration stack and $$$1$$$ poison stack at the end of the second round. So, the $$$hp$$$ will decrease by $$$X + P\\cdot 1 - R\\cdot 1 \u003d 1010$$$ this round. Overall, the health of the boss decreased by $$$1011 + 1010 \u003d 2021$$$.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eNow let\u0027s look at what will happen if we cast this spell during the second round.\u003c/p\u003e\u003cul\u003e\u003cli\u003e During the first round, no spells are applied, so at the end of this round there will be $$$0$$$ regeneration stacks, and $$$0$$$ poison stacks. Therefore, the $$$hp$$$ will decrease by $$$X + P\\cdot 0 - R\\cdot 0 \u003d 1010$$$ this round.\u003c/li\u003e\u003cli\u003e\u003cp\u003eAt the beginning of the second round, the boss will cast the \"Regeneration\" spell, so that there will be one regeneration stack after that. Then, we will we apply a \"Poison\" spell, decreasing the number of regeneration stacks by one. So, there will be $$$0$$$ regeneration stacks and $$$1$$$ poison stack at the end of the second round. Therefore, the $$$hp$$$ will decrease by $$$X + P\\cdot 1 - R\\cdot 0 \u003d 1011$$$ this round. Overall, the health of the boss decreased by $$$1010 + 1011 \u003d 2021$$$ again.\u003c/p\u003e\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eSo, no matter when we cast the \"Poison\" spell in this sample, we will still decrease the $$$hp$$$ by $$$2021$$$.\u003c/p\u003e"}}]}