← 返回题目列表

Codeforces · 1411/D

D. 污垢动物园

中文机器翻译题面 查看原题

目前,XXOC 的 rap 是由零、一和问号组成的字符串。不幸的是,仇恨者会仇恨。他们会为每次出现子序列 01 写下 $$$x$$$ 愤怒评论,为每次出现子序列 10 写下 $$$y$$$ 愤怒评论。您应该将所有问号替换为 0 或 1,这样愤怒评论的数量会尽可能少。

字符串 $$$b$$$ 是字符串 $$$a$$$ 的子序列,如果它可以通过从 $$$a$$$ 中删除一些字符来获得。如果剩余字符的位置集不同,则认为子序列的两次出现是不同的。

输入

第一行包含字符串 $$$s$$$ — XXOC 的说唱 ($$$1 \le |s| \leq 10^5$$$)。第二行包含两个整数 $$$x$$$ 和 $$$y$$$ - XXOC 在每次出现 01 和 10 时收到的愤怒评论数量 ($$$0 \leq x, y \leq 10^6$$$)。

输出

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

示例

输入 #1

0?1
2 3

输出 #1

4

输入 #2

?????
13 37

输出 #2

0

输入 #3

?10?
239 7

输出 #3

28

输入#4

01101001
5 7

输出#4

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$$$。