Estás a jogar e vais enfrentar o chefe secreto. Neste jogo, o chefe não te ataca, mas pode lançar feitiços de regeneração.
A luta tem exatamente $N$ rondas. Em cada ronda podem ocorrer as seguintes ações, por esta ordem:
- O chefe pode optar por lançar o feitiço «Regeneração».
- Podes optar por lançar o feitiço «Veneno», se ainda tiveres mana.
- Atacas com uma espada, causando $X$ de dano.
- Aplicam-se todos os efeitos passivos.
Há dois tipos de efeitos passivos: regeneração e veneno. Os efeitos acumulam-se, pelo que o estado atual do chefe pode ser descrito por três inteiros: pontos de vida atuais ($hp$), cargas de veneno atuais ($p$) e cargas de regeneração atuais ($r$). No início não há cargas de veneno nem de regeneração ($p=r=0$). Cada carga de veneno causa $P$ de dano, e cada carga de regeneração recupera $R$ pontos de vida.
Os feitiços têm os seguintes efeitos:
«Regeneração»: aumenta em $1$ o número de cargas de regeneração $r$.
«Veneno»: aumenta em $1$ o número de cargas de veneno $p$. Se o número de cargas de regeneração for estritamente positivo ($r>0$), diminui-o em $1$.
Após a ronda, $hp$ diminui em $X+P\cdot p-R\cdot r$ (este valor pode ser negativo se o chefe recuperar vida mais depressa do que causas dano).
Sabes se o chefe lançará «Regeneração» em cada ronda. Tens mana suficiente para lançar «Veneno» $K$ vezes (não tens de gastar toda a mana). Qual é o maior dano total que podes causar ao chefe, ou seja, o valor máximo de $hp_{start}-hp_{end}$? Assume $hp_{start}=10^{1000}$, pelo que não podes efetivamente matar o chefe em $N$ rondas. A vida do chefe pode ultrapassar o valor inicial (ver o terceiro exemplo).
Entrada
A primeira linha contém 5 inteiros $N,X,R,P,K$ ($1\le N,X,R,P\le10^6$, $0\le K\le N$).
A segunda linha contém uma cadeia binária de comprimento $N$. O seu $i$-ésimo carácter é 1 se o chefe lançar «Regeneração» no início da ronda $i$, e 0 caso contrário.
Saída
Imprime um inteiro: o maior dano total que podes causar durante a luta.
Exemplos
Entrada 1
2 1010 1 1 1 01
Saída 1
2021
Entrada 2
3 2 1 1 1 001
Saída 2
8
Entrada 3
10 1 10 40 1 1111111111
Saída 3
-40
Nota
Analisemos o primeiro exemplo. Podemos lançar «Veneno» no máximo uma vez. Vejamos o que acontece se o lançarmos na primeira ronda.
Na primeira ronda lançamos «Veneno», pelo que no fim há 0 cargas de regeneração e 1 de veneno. Assim, $hp$ diminui em $X+P\cdot1-R\cdot0=1011$.
No início da segunda ronda o chefe lança «Regeneração», pelo que no fim há 1 carga de regeneração e 1 de veneno. Assim, $hp$ diminui em $X+P\cdot1-R\cdot1=1010$. No total, a vida do chefe diminuiu em $1011+1010=2021$.
Vejamos agora o que acontece se lançarmos o feitiço na segunda ronda.
Na primeira ronda não são lançados feitiços, pelo que no fim há 0 cargas de regeneração e 0 de veneno. Assim, $hp$ diminui em $X+P\cdot0-R\cdot0=1010$.
No início da segunda ronda o chefe lança «Regeneração», passando a haver 1 carga de regeneração. Depois lançamos «Veneno», reduzindo esse número em um. No fim há 0 cargas de regeneração e 1 de veneno. Assim, $hp$ diminui em $X+P\cdot1-R\cdot0=1011$. No total, a vida do chefe volta a diminuir em $1010+1011=2021$.
Portanto, neste exemplo, independentemente de quando lançamos «Veneno», diminuímos a vida em 2021.