Задана строка \(s\) длины \(n\), состоящая только из символов 0 и 1.
Вы выполняете следующую операцию до тех пор, пока строка не станет пустой: взять последовательный подотрезок одинаковых символов, удалить его из строки и склеить оставшиеся две части (любая из оставшихся частей может быть пустой). Например, если удалить подстроку 111 из строки 111110, то получится строка 110. За удаление строки длины \(l\) вы получаете \(a \cdot l + b\) очков.
Ваша задача — определить максимальное количество очков, которое вы можете набрать, если вы должны сделать заданную строку пустой.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество очков, которое вы можете набрать.
Примечание
В первом примере достаточно удалить всю строку целиком, тогда мы получим \(2 \cdot 3 + 0 = 6\) очков.
Во втором примере, если удалять символы по одному, то за каждый удаленный символ мы получим \((-2) \cdot 1 + 5 = 3\) очков, т.е. суммарно \(15\) очков.
В третьем примере удалим подстроку 00 из строки 100111, получим \(1 \cdot 2 + (-4) = -2\) очков, а строка будет равна 1111, удалив ее целиком получим \(1 \cdot 4 + (-4) = 0\) очков. Суммарно за \(2\) операции получили \(-2\) очков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2 0
000
5 -2 5
11001
6 1 -4
100111
|
6
15
-2
|