题目描述

题目译自 XV OI Olimpiada Informatyczna – II etap BBB

Bajtazar 的银行账户初始余额为 $p$，最终需达到 $q$，现有 $n$ 次交易的流水（由 '+' 和 '-' 组成，'+' 表示存入 1 拜塔拉，'-' 表示取出 1 拜塔拉）。需修正流水满足两个条件：

1. 初始余额 $p$ 经流水操作后，最终余额为 $q$，且过程中余额始终不低于 0；
2. 修正代价最小，可执行两种操作：
   • 花费 $x$ 秒将任一操作改为相反操作（'+'变'-'或'-'变'+'）；
   • 花费 $y$ 秒将最后一个操作移动到流水开头（可多次执行，每次移动一个末尾操作到开头）。

需计算修正流水的最少时间。

输入格式

1. 第一行：5 个整数 $n, p, q, x, y$（$1 \leq n \leq 10^6$，$0 \leq p, q \leq 10^6$，$1 \leq x, y \leq 1000$），分别表示交易次数、初始余额、目标最终余额、更改操作成本、移动操作成本；
2. 第二行：长度为 $n$ 的字符串 $s$，由 '+' 和 '-' 组成，代表当前流水。

输出格式

输出一行整数，表示最少修正时间。保证存在有效修正方案。

样例

输入

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

输出

3