У Даши есть \(10^{100}\) монет. Недавно она нашла бинарную строку \(s\) длины \(n\) и несколько операций, с помощью которых её можно изменять (каждую операцию можно делать сколько угодно раз):
- Заменить подстроку строки \(s\), равную 00, на 0 и получить \(a\) монет.
- Заменить подстроку строки \(s\), равную 11, на 1 и получить \(b\) монет.
- Удалить из строки \(s\) символ 0, заплатив за это \(c\) монет.
Оказалось, что при выполнении операций нужно соблюдать следующее правило:
- Запрещается делать две операции с номерами одинаковой чётности подряд. Операции пронумерованы числами от \(1\) до \(3\) в порядке, в котором они даны выше.
Определите максимальное количество монет, которое Даша может получить делая эти операции и не нарушая правило.
Выходные данные
Для каждого набора входных данных выведите ответ.
Примечание
В первом наборе входных данных одна из оптимальных последовательностей операций такая: 01101 \(\rightarrow\) 0101 \(\rightarrow\) 011 \(\rightarrow\) 01. Эта последовательность состоит из операций \(2\), \(3\) и \(2\) в таком порядке. Она удовлетворяет всем правилам и даёт \(3\) монеты. Можно показать, что нельзя получить больше монет, поэтому ответ \(3\).
Во втором наборе входных данных одна из оптимальных последовательностей операций такая: 110001 \(\rightarrow\) 11001 \(\rightarrow\) 1001 \(\rightarrow\) 101.
В третьем наборе входных данных одна из оптимальных последовательностей операций такая: 011110 \(\rightarrow\) 01110 \(\rightarrow\) 1110 \(\rightarrow\) 110 \(\rightarrow\) 11 \(\rightarrow\) 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 2 2 1
01101
6 4 3 5
110001
6 3 2 1
011110
|
3
11
4
|