Estás jugando a un juego y vas a luchar contra el jefe secreto. En este juego, el jefe no te ataca, pero puede lanzar hechizos de regeneración.
La lucha consta de exactamente $N$ rondas. En cada ronda pueden suceder las siguientes acciones, en este orden:
- El jefe puede elegir lanzar el hechizo «Regeneración».
- Puedes elegir lanzar el hechizo «Veneno» si te queda maná.
- Atacas con una espada, causando $X$ de daño.
- Se aplican todos los efectos pasivos.
Hay dos tipos de efectos pasivos: regeneración y veneno. Los efectos se acumulan, por lo que el estado actual del jefe se describe mediante tres enteros: puntos de vida actuales ($hp$), acumulaciones actuales de veneno ($p$) y de regeneración ($r$). Al principio no hay acumulaciones de veneno ni de regeneración ($p=r=0$). Cada acumulación de veneno causa $P$ de daño y cada acumulación de regeneración cura $R$ puntos de vida.
Los hechizos tienen estos efectos:
«Regeneración»: aumenta en $1$ el número de acumulaciones de regeneración $r$.
«Veneno»: aumenta en $1$ el número de acumulaciones de veneno $p$. Si el número de acumulaciones de regeneración es estrictamente positivo ($r>0$), lo reduce en $1$.
Tras la ronda, $hp$ disminuye en $X+P\cdot p-R\cdot r$ (este valor puede ser negativo si el jefe se cura más rápido de lo que causas daño).
Sabes si el jefe lanzará «Regeneración» en cada ronda. Tienes maná suficiente para lanzar «Veneno» $K$ veces (no tienes que gastarlo todo). ¿Cuál es el mayor daño total que puedes causar, es decir, el máximo valor de $hp_{start}-hp_{end}$? Supón que $hp_{start}=10^{1000}$, así que no puedes matar realmente al jefe en $N$ rondas. Su vida puede superar el valor inicial (véase el tercer ejemplo).
Entrada
La primera línea contiene 5 enteros $N,X,R,P,K$ ($1\le N,X,R,P\le10^6$, $0\le K\le N$).
La segunda línea contiene una cadena binaria de longitud $N$. Su carácter $i$ es 1 si el jefe lanza «Regeneración» al principio de la ronda $i$, y 0 en caso contrario.
Salida
Imprime un entero: el mayor daño total que puedes causar durante la lucha.
Ejemplos
Entrada 1
2 1010 1 1 1 01
Salida 1
2021
Entrada 2
3 2 1 1 1 001
Salida 2
8
Entrada 3
10 1 10 40 1 1111111111
Salida 3
-40
Nota
Veamos el primer ejemplo. Podemos lanzar «Veneno» como máximo una vez. Veamos qué ocurre si lo lanzamos en la primera ronda.
En la primera ronda lanzamos «Veneno», así que al final hay 0 acumulaciones de regeneración y 1 de veneno. Por tanto, $hp$ disminuye en $X+P\cdot1-R\cdot0=1011$.
Al principio de la segunda ronda el jefe lanza «Regeneración», así que al final hay 1 acumulación de regeneración y 1 de veneno. Entonces $hp$ disminuye en $X+P\cdot1-R\cdot1=1010$. En total, la vida del jefe disminuye en $1011+1010=2021$.
Veamos ahora qué ocurre si lo lanzamos en la segunda ronda.
En la primera ronda no se lanzan hechizos, así que al final hay 0 acumulaciones de regeneración y 0 de veneno. Por tanto, $hp$ disminuye en $X+P\cdot0-R\cdot0=1010$.
Al principio de la segunda ronda el jefe lanza «Regeneración», tras lo cual hay 1 acumulación de regeneración. Después lanzamos «Veneno», reduciendo esa cantidad en uno. Al final hay 0 acumulaciones de regeneración y 1 de veneno. Por tanto, $hp$ disminuye en $X+P\cdot1-R\cdot0=1011$. En total, la vida del jefe vuelve a disminuir en $1010+1011=2021$.
Por tanto, en este ejemplo, independientemente de cuándo lancemos «Veneno», reduciremos la vida en 2021.