当前没有测试数据。

D - Shift vs. CapsLock

得分：400分

题目描述

你的计算机键盘上有三个按键：'a'键、Shift键和Caps Lock键。Caps Lock键上有一个灯。 初始情况下，Caps Lock键上的灯是关闭的，并且屏幕上显示一个空字符串。

你可以任意次数以任意顺序执行以下三个操作：

• 按下'a'键花费X毫秒。如果Caps Lock键上的灯是关闭的，则将字符'a'添加到屏幕上的字符串；如果灯是打开的，则添加字符'A'。
• 同时按下'a'键和Shift键花费Y毫秒。如果Caps Lock键上的灯是关闭的，则在屏幕上的字符串末尾添加字符'A'；如果灯是打开的，则添加字符'a'。
• 按下Caps Lock键花费Z毫秒。如果Caps Lock键上的灯是关闭的，则打开它；如果灯是打开的，则关闭它。

给定一个由'A'和'a'组成的字符串S，确定至少需要花费多少毫秒才能使屏幕上显示的字符串与S相等。

约束条件

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

输入

输入从标准输入中以以下格式给出：

X Y Z
S

输出

打印答案。

示例

输入1:

1 3 3
AAaA

输出1:

9

这是使屏幕上的字符串与AAaA相等的最短时间序列，总共花费了9毫秒。

• 花费3毫秒按下Caps Lock键。Caps Lock键上的灯打开。
• 花费1毫秒按下'a'键。将字符'A'添加到屏幕上的字符串。
• 花费1毫秒按下'a'键。将字符'A'添加到屏幕上的字符串。
• 花费3毫秒按下Shift键和'a'键。将字符'a'添加到屏幕上的字符串。
• 花费1毫秒按下'a'键。将字符'A'添加到屏幕上的字符串。

输入2:

1 1 100
aAaAaA

输出2:

6

输入3:

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

输出3:

40