|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||6||3||3||50.000%|
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:
You are to calculate the minimum amount of time the bank teller needs to correct the bank statement.
The bank teller can:
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:
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.
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.
9 2 3 2 1 ---++++++