Vous jouez à un jeu et allez affronter le boss secret. Dans ce jeu, le boss ne vous attaque pas, mais il peut lancer des sorts de régénération.

Le combat comporte exactement $N$ tours. À chaque tour, les actions suivantes peuvent se produire dans cet ordre :

1. Le boss peut choisir de lancer le sort « Régénération ».
2. Vous pouvez choisir de lancer le sort « Poison » s'il vous reste du mana.
3. Vous attaquez avec une épée et infligez $X$ dégâts.
4. Tous les effets passifs sont appliqués.

Il existe deux types d'effets passifs : régénération et poison. Les effets se cumulent, donc l'état actuel du boss peut être décrit par trois entiers : ses points de vie actuels ($hp$), ses charges de poison actuelles ($p$) et ses charges de régénération actuelles ($r$). Au début du combat, il n'y a aucune charge de poison ni de régénération ($p=r=0$). Chaque charge de poison inflige $P$ dégâts et chaque charge de régénération soigne $R$ points de vie.

Les sorts ont les effets suivants :

« Régénération » : augmente de $1$ le nombre de charges de régénération $r$.

« Poison » : augmente de $1$ le nombre de charges de poison $p$. Si le nombre de charges de régénération est strictement positif ($r>0$), il est diminué de $1$.

Après le tour, $hp$ diminue de $X+P\cdot p-R\cdot r$ (cette valeur peut être négative si le boss se soigne plus vite que vous n'infligez des dégâts).

Pour chaque tour, vous savez si le boss lancera « Régénération ». Vous avez assez de mana pour lancer « Poison » $K$ fois (vous n'êtes pas obligé de tout utiliser). Quels dégâts totaux maximaux pouvez-vous infliger, autrement dit quelle est la valeur maximale de $hp_{start}-hp_{end}$ ? Supposez que $hp_{start}=10^{1000}$ : vous ne pouvez donc pas réellement tuer le boss en $N$ tours. Ses points de vie peuvent dépasser leur valeur initiale (voir le troisième exemple).

Entrée

La première ligne contient 5 entiers $N,X,R,P,K$ ($1\le N,X,R,P\le10^6$, $0\le K\le N$).

La deuxième ligne contient une chaîne binaire de longueur $N$. Son $i$-ème caractère vaut 1 si le boss lance « Régénération » au début du $i$-ème tour, et 0 sinon.

Sortie

Affichez un entier : les dégâts totaux maximaux que vous pouvez infliger pendant le combat.

Exemples

Entrée 1

2 1010 1 1 1
01

Sortie 1

2021

Entrée 2

3 2 1 1 1
001

Sortie 2

8

Entrée 3

10 1 10 40 1
1111111111

Sortie 3

-40

Remarque

Considérons le premier exemple. Nous pouvons lancer « Poison » au plus une fois. Voyons ce qui se passe si nous le lançons au premier tour.

• Au premier tour, nous lançons « Poison » ; il y a donc 0 charge de régénération et 1 charge de poison à la fin du tour. Ainsi, $hp$ diminue de $X+P\cdot1-R\cdot0=1011$.

• Au début du deuxième tour, le boss lance « Régénération » ; il y a donc 1 charge de régénération et 1 charge de poison à la fin du tour. Ainsi, $hp$ diminue de $X+P\cdot1-R\cdot1=1010$. Au total, les points de vie ont diminué de $1011+1010=2021$.

Voyons maintenant ce qui se passe si nous le lançons au deuxième tour.

• Au premier tour, aucun sort n'est lancé ; il y a donc 0 charge de régénération et 0 charge de poison à la fin du tour. Ainsi, $hp$ diminue de $X+P\cdot0-R\cdot0=1010$.

• Au début du deuxième tour, le boss lance « Régénération », ce qui donne 1 charge de régénération. Nous lançons ensuite « Poison », réduisant ce nombre d'une unité. À la fin, il y a 0 charge de régénération et 1 charge de poison. Ainsi, $hp$ diminue de $X+P\cdot1-R\cdot0=1011$. Au total, les points de vie ont de nouveau diminué de $1010+1011=2021$.

Ainsi, dans cet exemple, quel que soit le moment où nous lançons « Poison », nous réduisons les points de vie de 2021.