103033: [Atcoder]ABC303 D - Shift vs. CapsLock

Problem Statement

Your computer has a keyboard with three keys: 'a' key, Shift key, and Caps Lock key. The Caps Lock key has a light on it. Initially, the light on the Caps Lock key is off, and the screen shows an empty string.

You can do the following three actions any number of times in any order:

• Spend $X$ milliseconds to press only the 'a' key. If the light on the Caps Lock key is off, a is appended to the string on the screen; if it is on, A is.
• Spend $Y$ milliseconds to press the 'a' key and Shift key simultaneously. If the light on the Caps Lock key is off, A is appended to the string on the screen; if it is on, a is.
• Spend $Z$ milliseconds to press the Caps Lock key. If the light on the Caps Lock key is off, it turns on; if it is on, it turns off.

Given a string $S$ consisting of A and a, determine at least how many milliseconds you need to spend to make the string shown on the screen equal to $S$.

Constraints

• $1 \leq X,Y,Z \leq 10^9$
• $X$, $Y$, and $Z$ are integers.
• $1 \leq |S| \leq 3 \times 10^5$
• $S$ is a string consisting of A and a.

Input

The input is given from Standard Input in the following format:

$X$ $Y$ $Z$
$S$

Output

Print the answer.

Sample Input 1

1 3 3
AAaA

Sample Output 1

9

The following sequence of actions makes the string on the screen equal to AAaA in $9$ milliseconds, which is the shortest possible.

• Spend $Z(=3)$ milliseconds to press the CapsLock key. The light on the Caps Lock key turns on.
• Spend $X(=1)$ milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend $X(=1)$ milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend $Y(=3)$ milliseconds to press the Shift key and 'a' key simultaneously. a is appended to the string on the screen.
• Spend $X(=1)$ milliseconds to press the 'a' key. A is appended to the string on the screen.

Sample Input 2

1 1 100
aAaAaA

Sample Output 2

6

Sample Input 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

Sample Output 3

40

问题描述

你的电脑有一个键盘，有三个键：'a' 键，Shift 键和 Caps Lock 键。Caps Lock 键上有一个灯。起初，Caps Lock 键上的灯是关闭的，屏幕上显示一个空字符串。

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

• 花费 $X$ 毫秒按下 'a' 键。如果 Caps Lock 键上的灯关闭，a 会被添加到屏幕上的字符串；如果灯亮着，则添加A。
• 花费 $Y$ 毫秒同时按下 'a' 键和 Shift 键。如果 Caps Lock 键上的灯关闭，A 会被添加到屏幕上的字符串；如果灯亮着，则添加a。
• 花费 $Z$ 毫秒按下 Caps Lock 键。如果 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

以下操作序列在 $9$ 毫秒内使屏幕上的字符串等于 AAaA，这是最短可能的时间。

• 花费 $Z(=3)$ 毫秒按下 CapsLock 键。Caps Lock 键上的灯打开。
• 花费 $X(=1)$ 毫秒按下 'a' 键。A 被添加到屏幕上的字符串。
• 花费 $X(=1)$ 毫秒按下 'a' 键。A 被添加到屏幕上的字符串。
• 花费 $Y(=3)$ 毫秒同时按下 Shift 键和 'a' 键。a 被添加到屏幕上的字符串。
• 花费 $X(=1)$ 毫秒按下 'a' 键。A 被添加到屏幕上的字符串。

样例输入 2

1 1 100
aAaAaA

样例输出 2

6

样例输入 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

样例输出 3

40