Byteasar has an account at The Byteotian Bit Bank (BBB in short). At the beginning there were $p$ and at the end $q$ bythalers in the account. Each transaction was either a deposit or a withdrawal of one bythaler. The account's balance was never negative. A bank teller has prepared a bank statement: a strip of paper with a sequence of pluses and minuses in it (a plus denotes a deposit while minus a withdrawal of one bythaler). Soon it turned out, that some transactions were not entered correctly. The bank teller cannot print another statement, but has to correct the one already printed instead. The statement needs not be consistent with the truth, it will suffice if the sequence of transactions satisfies the following two conditions:

• the final balance is consistent with the initial balance and the sequence of transactions in the statement,
• according to the sequence of transactions in the statement, the account's balance was never negative.

You are to calculate the minimum amount of time the bank teller needs to correct the bank statement.

The bank teller can:

• in $x$ seconds turn an arbitrarily chosen transaction to its opposite, or
• in $y$ seconds remove the last transaction and put it at the beginning of the statement.

If, for example, $p=2$, $q=3$, then --++-+-++-+-+ is a correct statement. On the other hand the statement ---++++++ is incorrect, because the account's balance would become negative after the third transaction, and furthermore the final balance should be 3, not 5. It can be, however, corrected by turning the second to last symbol to its opposite and placing the last transaction at the beginning of the statement.

Write a programme that:

• reads the current bank statement for Byteasar's account (a sequence of pluses and minuses) as well as the numbers $p$, $q$, $x$ and $y$ from the standard input.
• writes out to the standard output the minimum number of seconds needed to correct the statement in a way such that the initial and final balance are consistent and that the balance is never negative.

Input

The first line contains $5$ integers $n$, $p$, $q$, $x$ and $y$ ($1 ≤ n ≤ 1\,000\,000$, $0 ≤ p,q ≤ 1\,000\,000$, $1 ≤ x,y ≤ 1\,000$), separated by single spaces and denoting respectively: the number of transactions done by Byteasar, initial and final account balance and the number of seconds needed to perform a single turn (change of sign) and move of transaction to the beginning. The second line contains a sequence of $n$ signs (each a plus or a minus), with no spaces in-between.

Output

The first and last output line should contain one integer, the minimum number of seconds needed to correct the statement. If no corrections are necessary, the number is zero. You may assume that a proper sequence of modifications exists for each test data.

Example

Input

9 2 3 2 1
---++++++

Output

3