Мишка Лимак подготавливает задачи для соревнования по программированию. Принято, что в задачах не упоминаются названии компании-спонсора соревнования, поэтому Лимак собирается изменить некоторые слова, чтобы удовлетворить этому ограничению. Чтобы условие все еще можно было читать, он хочет изменить каждое слово как можно меньше.
У Лимака есть слово s, состоящее из заглавных букв латинского алфавита. За один шаг он может поменять местами две соседние буквы в слове. Например, он может преобразовать слово «ABBC» в «BABC» или «ABCB» за один шаг.
Лимак хочет за несколько шагов преобразовать слово так, чтобы в нем не встречалась подстрока «VK» (то есть, не было бы буквы «V», сразу за которой идет буква «K»). Можно показать, что это возможно сделать с любым словом s.
Какое минимальное число шагов должен сделать Лимак для этого?
Выходные данные
Выведите одно целое число — минимальное число шагов, которое должен сделать Лимак для того, чтобы получить слово без подстроки «VK».
Примечание
В первом примере начальное слово — «VKVK». Минимально возможное число шагов равно 3. Оптимальная последовательность шагов показана ниже:
- Поменять местами две последние буквы. Слово станет равно «VKKV».
- Поменять местами две первые буквы. Слово станет равно «KVKV».
- Поменять местами вторую и третью буквы. Слово станет равно «KKVV». Очевидно, в слове теперь нет подстроки «VK».
Во втором примере есть две оптимальные последовательности шагов. Одна из них это «BVVKV» → «VBVKV» → «VVBKV». Другая — «BVVKV» → «BVKVV» → «BKVVV».
В пятом примере можно оставить слово как есть.