Shift 与 Caps Lock

题目描述

你的电脑有一个键盘,包含三个按键:'a' 键、Shift 键和 Caps Lock 键。Caps Lock 键上有一个指示灯。

最初,Caps Lock 键的指示灯是灭的,屏幕上显示空字符串。

你可以任意次数、任意顺序执行以下三种操作:

• 花费 $X$ 毫秒只按 'a' 键。如果 Caps Lock 键的指示灯是灭的,则在屏幕上的字符串末尾追加 a;如果是亮的,则追加 A。
• 花费 $Y$ 毫秒同时按 'a' 键和 Shift 键。如果 Caps Lock 键的指示灯是灭的,则在屏幕上的字符串末尾追加 A;如果是亮的,则追加 a。
• 花费 $Z$ 毫秒按 Caps Lock 键。如果指示灯是灭的,它就会亮起;如果是亮的,它就会熄灭。

给定一个由 A 和 a 组成的字符串 $S$,求使屏幕上的字符串等于 $S$ 所需的最少毫秒数。

输入格式

输入按以下格式从标准输入给出:

X Y Z
S

输出格式

输出答案。

样例

1 3 3
AAaA

9

以下操作序列用 $9$ 毫秒使屏幕上的字符串变为 AAaA,这是最短的。

花费 $Z(=3)$ 毫秒按 Caps Lock 键。Caps Lock 键的指示灯亮起。

花费 $X(=1)$ 毫秒按 'a' 键。屏幕上的字符串末尾追加 A。

花费 $X(=1)$ 毫秒按 'a' 键。屏幕上的字符串末尾追加 A。

花费 $Y(=3)$ 毫秒同时按 Shift 键和 'a' 键。屏幕上的字符串末尾追加 a。

花费 $X(=1)$ 毫秒按 'a' 键。屏幕上的字符串末尾追加 A。

1 1 100
aAaAaA

6

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

40

数据范围

• $1 \leq X,Y,Z \leq 10^9$
• $X$,$Y$,$Z$ 是整数。
• $1 \leq |S| \leq 3 \times 10^5$
• $S$ 是由 A 和 a 组成的字符串。