题目描述

这题是动态规划，大家做吧

强哥电脑的键盘和别人都不同,只有三个键：a 键，Shift 键，大写锁定键。大写锁定键上有一个指示灯。最初，大写锁定键上的灯没亮，电脑屏幕上有一个空字符串。

强哥可以按任意顺序做下列三种动作任意多次：

• 花 $X$ 毫秒按 a 键。若大写锁定键上的灯没亮, 字符 a 会被加到屏幕上字符串的末尾， 若灯亮了，字符 A 会被加到屏幕上字符串的末尾。
• 花 $Y$ 毫秒同时按 a 键和 Shift 键。 若大写锁定键上的灯没亮, 字符 A 会被加到屏幕上字符串的末尾， 若灯亮了，字符 a 会被加到屏幕上字符串的末尾。
• 花 $Z$ 毫秒按大写锁定键。若大写锁定键上的指示灯没亮，它会变亮；否则它会不亮。

给你一个由 A 和 a 构成的字符串 $S$，求你至少要花多少毫秒才能让屏幕上的字符串等于 $S$。

输入格式

• $1 \le X,Y,Z \le {10^9}$
• $X,Y,Z$均为整数
• 字符串S的长度 不超过 $3 \times {10^5}$
• 字符串S只由A和a组成

输入 X，Y, Z 以及字符串S

输出格式

最少需要花的毫秒数

1 3 3
AAaA

9

1 1 100
aAaAaA

6

提示