你有一个字符串 $$$a_1, a_2, \dots, a_n$$$,由零和一组成。
让我们将连续元素序列 $$$a_i, a_{i + 1}, \ldots, a_j$$$ ($$$1\leq i\leq j\leq n$$$) 称为字符串 $$$a$$$ 的子字符串。
您可以多次应用以下操作:
- 选择字符串 $$$a$$$ 的某些子字符串(例如,您可以选择整个字符串)并将其反转,为此支付 $$$x$$$ 硬币(例如,«0101101» $$$\to$$$ «0111001»);
- 选择字符串 $$$a$$$ 的某个子字符串(例如,您可以选择整个字符串或仅选择一个符号)并将每个符号替换为相反的符号(零被 1 替换,1 被零替换),并为其支付 $$$y$$$ 硬币(例如,«0101101» $$$\to$$$ «0110001»)。
您可以按任意顺序应用这些操作。允许对同一子字符串多次应用操作。
要获得仅由 1 组成的字符串,您至少需要花费多少金币?
输入
输入的第一行包含整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \leq n \leq 300\,000, 0 \leq x, y \leq 10^9$$$) - 字符串长度、第一个操作的成本(子串反转)和第二个操作的成本(反转子串的所有元素)子串)。
第二行包含长度为 $$$n$$$ 的字符串 $$$a$$$,由零和一组成。
输出
打印单个整数 - 获取仅由 1 组成的字符串所需的最小总操作成本。如果不需要执行任何操作,则打印$$$0$$$。
示例
输入 #1
5 1 10 01000
输出 #1
11
输入 #2
5 10 1 01000
输出 #2
2
输入 #3
7 2 3 1111111
输出 #3
0
注意
在第一个示例中,首先需要反转子字符串 $$$[1 \dots 2]$$$,然后需要反转子字符串 $$$[2 \dots 5]$$$。
然后字符串更改如下:
«01000» $$$\至$$$ «10000» $$$\至$$$ «11111»。
总运营成本为 $$$1 + 10 = 11$$$。
在第二个示例中,首先需要反转子字符串 $$$[1 \dots 1]$$$,然后需要反转子字符串 $$$[3 \dots 5]$$$。
然后字符串更改如下:
«01000» $$$\至$$$ «11000» $$$\至$$$ «11111»。
总成本为 $$$1 + 1 = 2$$$。
在第三个示例中,字符串已经仅由 1 组成,因此答案是 $$$0$$$。