[POI2008]账本BBB

有一份长度为 $n$ 的账单，其中字符 + 表示存入 $1$ 元，字符 - 表示取出 $1$ 元。账户的初始余额为 $p$ 元，所有交易完成后的余额应为 $q$ 元，但现在发现账单存在问题。

你需要修改账单，使其满足以下条件：

• 执行账单中的任意一笔交易后，账户余额均不会为负数；
• 执行完所有交易后，账户余额恰好为 $q$ 元。

你可以任意次执行以下两种操作：

1. 将账单中的某个字符取反，即把 + 改为 -，或把 - 改为 +，每次耗时 $x$；
2. 将账单的最后一个字符移动到最前面，每次耗时 $y$。

请计算将账单修改正确所需的最少总时间。

输入格式

第一行包含五个整数 $n$、$p$、$q$、$x$、$y$，依次表示交易数、初始余额、最终余额、翻转一个字符所需的时间，以及将最后一个字符移动到最前面所需的时间。

第二行包含一个长度为 $n$、仅由字符 + 和 - 组成且不含空格的字符串，表示原账单。

输出格式

输出一个整数，表示使账户余额始终非负且最终余额为 $q$ 所需的最少总时间。

样例输入

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

样例输出

3

数据范围

• $1\le n\le 10^6$；
• $0\le p,q\le 10^6$；
• $1\le x,y\le 10^3$；
• $|p-q|\le n$；
• $n+p+q$ 为偶数。

来源与许可

本题为 POI 2008 试题「账本BBB」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

3