Вам дана бинарная строка \(s\) длины \(n\).
Пусть \(d_i\) — число, в десятичной системе счисления записываемое как \(s_i s_{i+1}\) (возможно, с ведущим нулем). Определим \(f(s)\) как сумму всех корректных значений \(d_i\). Иными словами, \(f(s) = \sum\limits_{i=1}^{n-1} d_i\).
Например, для строки \(s = 1011\):
- \(d_1 = 10\) (десять);
- \(d_2 = 01\) (один);
- \(d_3 = 11\) (одиннадцать);
- \(f(s) = 10 + 01 + 11 = 22\).
За одну операцию вы можете поменять местами любые два соседних символа строки. Найдите минимально возможное значение \(f(s)\), которое может быть получено после не более чем \(k\) операций.
Выходные данные
Для каждого набора входных данных выведите минимально возможное значение \(f(s)\) после не более чем \(k\) операций.
Примечание
- В первом примере делать операции нельзя, поэтому оптимальный ответ — сама строка \(s\). \(f(s) = f(1010) = 10 + 01 + 10 = 21\).
- Во втором примере одно из оптимальных решений — строка «0011000». Для данной строки значение \(f\) равно \(22\).
- В третьем примере одно из оптимальных решений — строка «00011». Для данной строки значение \(f\) равно \(12\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 0
1010
7 1
0010100
5 2
00110
|
21
22
12
|