D. Грайм Зоопарк
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сейчас рэп ХХОСа представляет из себя строку из нулей, единиц и знаков вопроса. К сожалению, хейтеры не дремлют. За каждое вхождение подпоследовательности 01 в рэп ХХОСа хейтеры напишут $$$x$$$ гневных комментариев, а за каждое вхождение подпоследовательности 10 будет написано $$$y$$$ гневных комментариев. Вы должны заменить каждый знак вопроса на 0 либо 1, чтобы минимизировать число гневных комментариев, которые получит ХХОС.

Подпоследовательностью строки $$$a$$$ называется строка $$$b$$$, которая может получиться в результате удаления нескольких символов из строки $$$a$$$. Два вхождения подпоследовательности считаются разными, если различаются множества позиций оставленных символов.

Входные данные

В первой строке записан рэп ХХОСа — строка $$$s$$$ ($$$1 \le |s| \leq 10^5$$$). Во второй строке даны два целых числа $$$x$$$ и $$$y$$$ — количество гневных комментариев, которые ХХОС получит за каждую подпоследовательность 01 и 10, соответственно ($$$0 \leq x, y \leq 10^6$$$).

Выходные данные

В единственной строке выведите минимальное число гневных комментариев, которые может получить ХХОС.

Примеры
Входные данные
0?1
2 3
Выходные данные
4
Входные данные
?????
13 37
Выходные данные
0
Входные данные
?10?
239 7
Выходные данные
28
Входные данные
01101001
5 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$$$.