CF1411D.Grime Zoo

Currently, XXOC's rap is a string consisting of zeroes, ones, and question marks. Unfortunately, haters gonna hate. They will write $x$ angry comments for every occurrence of subsequence 01 and $y$ angry comments for every occurrence of subsequence 10. You should replace all the question marks with 0 or 1 in such a way that the number of angry comments would be as small as possible.

String $b$ is a subsequence of string $a$, if it can be obtained by removing some characters from $a$. Two occurrences of a subsequence are considered distinct if sets of positions of remaining characters are distinct.

目前，XXOC 的说唱是一段由数字 0、1 和问号 ? 组成的字符串。不幸的是，黑粉总会黑你。对于每一个子序列 01 的出现，他们会留下 $x$ 条愤怒评论；对于每一个子序列 10 的出现，他们会留下 $y$ 条愤怒评论。你需要将所有问号 ? 替换为 0 或 1，使得愤怒评论的总数尽可能少。

若字符串 $b$ 可通过从字符串 $a$ 中删除若干字符得到，则称 $b$ 是 $a$ 的一个子序列。若两个子序列出现所对应保留字符的位置集合不同，则认为它们是两个不同的出现。

The first line contains string $s$ — XXOC's rap ($1 \le |s| \leq 10^5$). The second line contains two integers $x$ and $y$ — the number of angry comments XXOC will recieve for every occurrence of 01 and 10 accordingly ($0 \leq x, y \leq 10^6$).

第一行包含字符串 $s$ — XXOC 的说唱内容（$1 \le |s| \leq 10^5$）。第二行包含两个整数 $x$ 和 $y$ — 分别表示每出现一次子串 01 和 10 时，XXOC 将收到的愤怒评论数（$0 \leq x, y \leq 10^6$）。

Output a single integer — the minimum number of angry comments.

输出一个整数——愤怒评论的最少数量。

In the first example one of the optimum ways to replace is 001. Then there will be $2$ subsequences 01 and $0$ subsequences 10. Total number of angry comments will be equal to $2 \cdot 2 + 0 \cdot 3 = 4$.

In the second example one of the optimum ways to replace is 11111. Then there will be $0$ subsequences 01 and $0$ subsequences 10. Total number of angry comments will be equal to $0 \cdot 13 + 0 \cdot 37 = 0$.

In the third example one of the optimum ways to replace is 1100. Then there will be $0$ subsequences 01 and $4$ subsequences 10. Total number of angry comments will be equal to $0 \cdot 239 + 4 \cdot 7 = 28$.

In the fourth example one of the optimum ways to replace is 01101001. Then there will be $8$ subsequences 01 and $8$ subsequences 10. Total number of angry comments will be equal to $8 \cdot 5 + 8 \cdot 7 = 96$.

在第一个例子中，一种最优的替换方式是 001。此时将有 $2$ 个子序列 01 和 $0$ 个子序列 10。愤怒评论的总数为 $2 \cdot 2 + 0 \cdot 3 = 4$。

在第二个例子中，一种最优的替换方式是 11111。此时将有 $0$ 个子序列 01 和 $0$ 个子序列 10。愤怒评论的总数为 $0 \cdot 13 + 0 \cdot 37 = 0$。

在第三个例子中，一种最优的替换方式是 1100。此时将有 $0$ 个子序列 01 和 $4$ 个子序列 10。愤怒评论的总数为 $0 \cdot 239 + 4 \cdot 7 = 28$。

在第四个例子中，一种最优的替换方式是 01101001。此时将有 $8$ 个子序列 01 和 $8$ 个子序列 10。愤怒评论的总数为 $8 \cdot 5 + 8 \cdot 7 = 96$。