Minimum Value Calculation by Replacing '!' in a Binary String

You are given a string S containing only 0, 1 and !. Each ! can independently be replaced with 0 or 1. After the replacement, every adjacent pair 01 costs x, every adjacent pair 10 costs y, and every other adjacent pair costs 0. Find the minimum total cost.

输入格式

The first line of input is S (length 1..100000, containing at least one !). The second line contains the non-negative 32-bit integers x and y.

输出格式

Output the minimum total cost.

样例 1

输入：

01!0
2 3

输出：

5

样例 2

输入：

!0!1
3 4

输出：

3

样例说明

For each position you only need the minimum prefix cost with the current position set to 0 or to 1; each transition only looks at the newly added last pair of characters.