D - Shift vs. CapsLock Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

あなたのパソコンのキーボードには、a キー・Shift キー・CapsLock キーの 3 種類のキーがあります。また、CapsLock キーにはランプが付いています。 初め、CapsLock キーのランプは OFF であり、パソコンの画面には空文字列が表示されています。

あなたは、以下の 3 種類の操作のうち 1 つを選んで実行するということを 0 回以上何度でも行うことができます。

  • X ミリ秒かけて a キーのみを押す。CapsLock キーのランプが OFF ならば画面の文字列の末尾に a が付け足され、ON ならば A が付け足される。
  • Y ミリ秒かけて Shift キーと a キーを同時に押す。CapsLock キーのランプが OFF ならば画面の文字列の末尾に A が付け足され、 ON ならば a が付け足される。
  • Z ミリ秒かけて CapsLock キーを押す。CapsLock キーのランプが OFF ならば ON に、ON ならば OFF に切り替わる。

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 キーを押す。CapsLock キーのランプが ON になる。
  • 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

Score : 400 points

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