Вам дана строка \(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\) и заменить каждый символ на противоположный ему (то есть нули заменяются на единицы, а единицы — на нули), заплатив за это \(y\) монет (например, «0101101» \(\to\) «0110001»).
Вы можете применять операции в любом порядке. Допустимо к одной и той же подстроке применять любую или обе операции неоднократно.
Какое минимальное количество монет потребуется потратить, чтобы получить строку, состоящую только из единиц?
Выходные данные
Выведите единственное целое число — минимальную суммарную стоимость изменений, необходимых для получения строки, состоящей только из единиц. Выведите \(0\), если не требуется совершать никаких изменений.
Примечание
В первом примере нужно сначала перевернуть подстроку \([1 \dots 2]\), а затем инвертировать подстроку \([2 \dots 5]\).
Тогда строка изменялась так:
«01000» \(\to\) «10000» \(\to\) «11111».
И затраченная стоимость соответственно равна \(1 + 10 = 11\).
Во втором примере нужно сначала инвертировать подстроку \([1 \dots 1]\), а затем инвертировать подстроку \([3 \dots 5]\).
Тогда строка изменялась так:
«01000» \(\to\) «11000» \(\to\) «11111».
И затраченная стоимость соответственно равна \(1 + 1 = 2\).
В третьем примере строка уже состоит только из единиц, поэтому ответ \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1 10
01000
|
11
|
|
2
|
5 10 1
01000
|
2
|
|
3
|
7 2 3
1111111
|
0
|