BBB

Time limit1sMemory limit128 MB

Summary

Find the minimum cost to fix a + and - statement so the balance starts at p, never goes negative, and ends at q, using character flips and rotations.

Level: Medium7 of 10
Topics: Greedy, Prefix sum, String
Solved: No attempts yet

Problem

Byteasar keeps an account at the Byteotian Bit Bank (BBB for short). The account began with $p$ bythalers and ended with $q$ bythalers. Every transaction was either a deposit or a withdrawal of exactly one bythaler, and the balance was never negative at any moment.

A teller printed a statement for the account: a strip of paper with a sequence of $n$ symbols, where + marks a deposit of one bythaler and - marks a withdrawal of one bythaler. It later turned out that some symbols had been entered incorrectly. The teller cannot print a new statement and must fix the printed one in place. The corrected statement need not match what really happened; it only has to satisfy both of these conditions:

the final balance is consistent with the initial balance $p$ and the sequence of transactions on the statement (that is, it equals $q$ );
reading the transactions from left to right, the balance is never negative.

The teller can make two kinds of edits:

flip any single chosen symbol to its opposite (+ becomes -, or - becomes +) in $x$ seconds;
take the last symbol of the statement and move it to the front in $y$ seconds.

For example, with $p = 2$ and $q = 3$ the statement --++-+-++-+-+ is already correct. The statement ---++++++ is not: after the third transaction the balance would be negative, and the final balance would be $5$ instead of $3$ . It can be repaired by flipping the second-to-last symbol and then moving the last symbol to the front.

Determine the minimum number of seconds the teller needs so that the statement becomes correct: the initial and final balances agree and the balance is never negative.

Input

The first line contains five integers $n$ , $p$ , $q$ , $x$ , and $y$ ( $1 \le n \le 10^6$ , $0 \le p, q \le 10^6$ , $1 \le x, y \le 10^3$ ), separated by single spaces: the number of transactions, the initial balance, the final balance, the time in seconds needed for one flip, and the time in seconds needed to move the last symbol to the front. The second line contains a string of $n$ characters, each + or -, with no spaces between them.

Output

Print a single integer: the minimum number of seconds needed to make the statement correct. If no edit is needed, print $0$ . A valid sequence of edits is guaranteed to exist.

Examples6

Example 1
Input
```
9 2 3 2 1
---++++++
```
Expected output
```
3
```
Example 2
Input
```
2 0 0 5 5
+-
```
Expected output
```
0
```
Example 3
Input
```
1 1 0 4 2
+
```
Expected output
```
4
```
Example 4
Input
```
4 0 2 100 1
-+++
```
Expected output
```
1
```
Example 5
Input
```
4 0 2 1 100
-+++
```
Expected output
```
2
```
Example 6
Input
```
5 100 101 3 2
-+-+-
```
Expected output
```
3
```