Сейчас рэп ХХОСа представляет из себя строку из нулей, единиц и знаков вопроса. К сожалению, хейтеры не дремлют. За каждое вхождение подпоследовательности 01 в рэп ХХОСа хейтеры напишут \(x\) гневных комментариев, а за каждое вхождение подпоследовательности 10 будет написано \(y\) гневных комментариев. Вы должны заменить каждый знак вопроса на 0 либо 1, чтобы минимизировать число гневных комментариев, которые получит ХХОС.
Подпоследовательностью строки \(a\) называется строка \(b\), которая может получиться в результате удаления нескольких символов из строки \(a\). Два вхождения подпоследовательности считаются разными, если различаются множества позиций оставленных символов.
Выходные данные
В единственной строке выведите минимальное число гневных комментариев, которые может получить ХХОС.
Примечание
В первом примере одним из оптимальных вариантов замены является 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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
0?1
2 3
|
4
|
|
2
|
?????
13 37
|
0
|
|
3
|
?10?
239 7
|
28
|
|
4
|
01101001
5 7
|
96
|