题目描述

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.

Task

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.

输入格式

The first line contains 5 integers $n,p,q,x$ and $y\ (1\le n\le 1\ 000\ 000$, $0\le p,q\le 1\ 000\ 000$, $1\le x,y\le 1000$), 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 signs (each a plus or a minus), with no spaces in-between.

输出格式

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.

题目大意

给定一个由 $+1$ 和 $-1$ 构成的长度为 $n$ 的序列，提供两种操作：

1. 将某一位取反，花销为 $x$；
2. 将最后一位移动到第一位，花销为 $y$。

要求最终 $p+S_n=q$，且 $p+S_i≥0\ (1≤i≤n)$，求最小花销。其中 $S_i=a_1+a_2+\cdots+a_i$。

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

3