Problem Description

For a string $ s $, consider performing the following $ 3 $ operations any number of times to create the string $ T $. Initially, $ s $ is an empty string.

1. Pay $ A $ yen to insert 0 at the beginning of $ s $.
2. Pay $ B $ yen to insert 1 at the end of $ s $.
3. Pay $ C $ yen to replace all 0s in $ s $ with 1s and all 1s in $ s $ with 0s.

Find the minimum amount of money needed to create the string $ T $.

Input Format

The input is given from the standard input in the following format:

$ A $ $ B $ $ C $ $ T $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

1 10 2
0011

Sample Output #1

6

Sample Input #2

5 2 8
0000100111100101100101100000100

Sample Output #2

169

Sample Input #3

1000000000 1000000000 50
11011001001001

Sample Output #3

14000000200

Notes/Hints

Constraints

• $ 1 ≦ A, B, C ≦ 10^{9} $
• $1 ≦ |T| ≦ 2 \times 10^{5}$
• $ T $ is a string consisting only of 0 and 1
• $ A, B, C $ are all integers

Partial Points

• If you correctly solve the dataset satisfying $ 1 ≦ |T| ≦ 10 $, you will be awarded $ 300 $ points.
• If you correctly solve the dataset without additional constraints, you will be awarded an additional $ 400 $ points.

Sample Explanation 1

• First, perform operation $ 1 $ twice. $ s $ becomes 00.
• Next, perform operation $ 3 $ once. $ s $ becomes 11.
• Finally, perform operation $ 1 $ twice to make $ s $ 0011, which matches $ T $. This procedure requires $ 1 + 1 + 2 + 1 + 1 = 6 $ yen, which is the minimum amount of money needed. This case satisfies the partial points constraint.

见题面 Input 部分

见题面 Output 部分