Shift vs. CapsLock

题目描述

你的电脑键盘有三个按键：'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$。

输入格式

输入从标准输入按如下格式给出： $X$ $Y$ $Z$ $S$

输出格式

输出答案。

1 3 3
AAaA

9

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$ 组成的字符串。下面的操作序列能以 $9$ 毫秒的时间使屏幕上的字符串等于 $AAaA$，这是最短的时间。

花费 $Z(=3)$ 毫秒按下 CapsLock 键。Caps Lock 指示灯变为打开。 花费 $X(=1)$ 毫秒按下 'a' 键。屏幕上追加了 $A$。 花费 $X(=1)$ 毫秒按下 'a' 键。屏幕上追加了 $A$。 花费 $Y(=3)$ 毫秒同时按下 Shift 键和 'a' 键。屏幕上追加了 $a$。 花费 $X(=1)$ 毫秒按下 'a' 键。屏幕上追加了 $A$。

标签: AtCoder|abc303D

来源

AtCoder|abc303D