CF1411D.Grime Zoo

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

输入格式

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$ ).

输出格式

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

输入输出样例

输入#1
```
0?1
2 3
```
输出#1
```
4
```
输入#2
```
?????
13 37
```
输出#2
```
0
```
输入#3
```
?10?
239 7
```
输出#3
```
28
```
输入#4
```
01101001
5 7
```
输出#4
```
96
```

说明/提示

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

首页