to Pay Respects

You are playing a game, and you are going to fight the secret boss. In this game, the boss does not attack you, but they can cast regeneration spells.

The fight consists of exactly $N$ rounds. In each round, the following actions can happen, in this order:

1. The boss can choose to cast the "Regeneration" spell.
2. You can choose to cast the "Poison" spell if you have any mana left.
3. You attack with a sword, dealing $X$ damage.
4. All the passive effects are applied.

There are two types of passive effects: regeneration and poison. The effects stack, so the state of the boss is described by three integers: current health $hp$, current poison stacks $p$, and current regeneration stacks $r$. At the start of the fight, there are no poison stacks and no regeneration stacks ($p=r=0$). Each poison stack deals $P$ damage, and each regeneration stack heals $R$ health points.

The spells have the following effects:

"Regeneration": increases the number of regeneration stacks $r$ by $1$.

"Poison": increases the number of poison stacks $p$ by $1$. If the number of regeneration stacks is strictly positive ($r > 0$), it decreases $r$ by $1$.

After each round, $hp$ decreases by $X + P \cdot p - R \cdot r$. This value can be negative if the boss heals faster than you deal damage.

For each round, you know whether the boss casts "Regeneration". You have enough mana to cast "Poison" $K$ times, and you do not have to use all of it. What is the largest total damage you can deal to the boss? In other words, find the maximum value of $hp_{start} - hp_{end}$. Assume $hp_{start} = 10^{1000}$, so you cannot actually kill the boss in $N$ rounds. The boss health can rise above the initial value (see the third sample).

The first line contains five integers $N$, $X$, $R$, $P$, $K$ ($1 \le N, X, R, P \le 10^6$, $0 \le K \le N$).

The second line contains a binary string of length $N$. The $i$-th character is 1 if the boss casts "Regeneration" at the beginning of the $i$-th round, and 0 otherwise.

Output one integer: the largest total damage you can deal during the fight.

Consider the first sample. You can cast "Poison" at most once. If you cast it in the first round, the boss loses $X + P \cdot 1 - R \cdot 0 = 1011$ health in that round, then $X + P \cdot 1 - R \cdot 1 = 1010$ in the second round, for a total of 2021. If you cast it in the second round, the boss loses 1010 in the first round and $X + P \cdot 1 - R \cdot 0 = 1011$ in the second round, which is also 2021. So the answer is 2021 either way.