to Pay Respects#13025

to Pay Respects

1 second
256 megabytes
Hard

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

The fight consists of exactly 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 damage.

  4. All the passive effects are applied.

There 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 (), current poison stacks () and current regeneration stacks (). At the beginning of the fight, there are no poison stacks and no regeneration stacks (p=r=0). Each poison stack deals damage, each regeneration stack heals health points.

Spells have the following effects:

"Regeneration": increase the number of regenerations stacks by .

"Poison": increase the number of poison stacks by . If the number of regeneration stacks is strictly positive (r > 0), then decrease it by .

After the round the will decrease 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 if the boss will cast "Regeneration". You have enough mana to cast "Poison" times (you don't have to use all of your mana). What's 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} = 10^{1000}, so you can't actually kill the boss in rounds. Boss can go higher than the initial value (see the third sample case).

Input

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

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

Output

Output a single integer — the largest total damage you can deal during the fight.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

Let's look at the first sample. We can cast the "Poison" spell at most once. Let's look at what will happen if we cast this spell during the first round.

  • During the first round, we apply a "Poison" spell, so at the end of this round there will be regeneration stacks, and poison stack. Therefore, the will decrease by X + P\cdot 1 - R\cdot 0 = 1011 this round.

  • At the beginning of the second round, the boss will cast the "Regeneration" spell, so there will be regeneration stack and poison stack at the end of the second round. So, the will decrease by X + P\cdot 1 - R\cdot 1 = 1010 this round. Overall, the health of the boss decreased by 1011 + 1010 = 2021.

Now let's look at what will happen if we cast this spell during the second round.

  • During the first round, no spells are applied, so at the end of this round there will be regeneration stacks, and poison stacks. Therefore, the will decrease by X + P\cdot 0 - R\cdot 0 = 1010 this round.

  • At 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 regeneration stacks and poison stack at the end of the second round. Therefore, the will decrease by X + P\cdot 1 - R\cdot 0 = 1011 this round. Overall, the health of the boss decreased by 1010 + 1011 = 2021 again.

So, no matter when we cast the "Poison" spell in this sample, we will still decrease the by .