#1122. [POI2008]账本BBB

内存限制:162 MiB 时间限制:10 Sec

题目描述

一个长度为n的记账单,+表示存¥1,-表示取¥1。现在发现记账单有问题。一开始本来已经存了¥p,并且知道最后账户上还有¥q。你要把记账单修改正确,使得 1:账户永远不会出现负数; 2:最后账户上还有¥q。你有2种操作: 1:对某一位取反,耗时x; 2:把最后一位移到第一位,耗时y。

输入格式

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

输出格式

修改消耗的时间

样例

样例输入


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

样例输出


			
3

数据范围与提示