Дана строка, состоящая из символов 0 и/или 1. Вам нужно покрасить каждый символ этой строки в один из двух цветов: красный или синий.
Если вы покрасите \(i\)-й символ в красный цвет, вы получите \(r_i\) монет. Если вы покрасите его в синий цвет, вы получите \(b_i\) монет.
После покраски строки из нее удаляются все символы синего цвета. Затем в полученной строке подсчитывается количество инверсий (т. е. количество пар символов, в которых левый символ в паре — 1, а правый символ — 0). За каждую инверсию вы должны заплатить \(1\) монету.
Какое максимальное количество монет вы можете заработать?
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество монет, которое вы можете заработать.
Примечание
Пояснения для наборов входных данных в примере из условия (синие символы подчеркнуты, красные — нет):
- \(0100\underline{0}1\underline{0}\);
- \(10\underline{11}1\);
- \(\underline{0}1\underline{00000000}\);
- \(0\underline{1}010000\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7
0100010
6 6 6 7 7 6 6
3 3 5 4 7 6 7
5
10111
9 8 5 7 5
4 4 7 8 4
10
0100000000
7 7 6 5 2 2 5 3 8 3
8 6 9 6 6 8 9 7 7 9
8
01010000
8 7 7 7 8 7 7 8
4 4 4 2 1 4 4 4
|
43
36
76
52
|