题目描述

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

Bajtazar 在拜托银行（简称 BBB）拥有账户，初始余额为 $p$ 拜塔拉，最终余额为 $q$ 拜塔拉。所有交易为存入或取出 $1$ 拜塔拉，账户余额从不低于 $0$。柜员需生成账户流水：一串加号（存入 $1$ 拜塔拉）和减号（取出 $1$ 拜塔拉）。但交易记录可能未正确登记。柜员无法重印流水，只能修正已有流水。流水无需反映真实交易，仅需满足：

• 最终余额与初始余额 $p$ 和流水操作一致。
• 流水操作下，账户余额从不低于 $0$。

你的任务是计算柜员修正流水的最短时间。柜员可：

• 花费 $x$ 秒将任一操作更改为相反操作（加变减或减变加）。
• 花费 $y$ 秒将最后操作移动到流水开头。

例如，若 $p=2, q=3$，流水 --++-+-++-+-+ 有效，而 ---++++++ 无效（第 $3$ 次操作后余额低于 $0$，最终余额 $5 \neq 3$）。可通过更改倒数第 $2$ 位为相反操作，再将最后操作移到开头进行修正。

编写程序：

• 从标准输入读取 Bajtazar 账户流水的当前状态（加减号序列）及 $p, q, x, y$。
• 输出到标准输出修正流水所需的最少时间，确保初始和最终余额一致，且余额从不低于 $0$。

输入格式

第一行包含 $5$ 个整数 $n, p, q, x, y$ $(1 \leq n \leq 1000000, 0 \leq p, q \leq 1000000, 1 \leq x, y \leq 1000)$，用单空格分隔，分别表示交易次数、初始余额、最终余额、更改操作和移动操作的秒数。第二行包含长度为 $n$ 的加号（+）和/或减号（-）序列，无空格。

输出格式

输出一行，包含一个整数，表示修正账户流水的最少时间（秒）。若流水无需修正，输出 $0$。保证测试数据存在有效修正方案。

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

3