Доктор Хаус в морге
Герой популярного телесериала доктор Хаус в очередной раз разыграл свою начальницу, доктора Кадди, и она решила немного наказать - разыграть его. Для этого она хочет отправить Хауса в морг рассортировать трупы, лежащие в нумерованных ячейках. Трупы бывают трёх типов мужские (обозначим их буквой m), женские (f) и детские (с). От Хауса требуется, чтобы сначала лежали все детские трупы, после них – все женские, и только потом – мужские.
Напомним, что доктор Хаус – инвалид с больной ногой, и таскать трупы (даже на каталках) ему нелегко. Поэтому сердобольная доктор Кадди решила проверить, какое минимальное число перекладок трупов ему придётся совершить (зная доктора Хауса как весьма неглупого человека, она догадывается, что он будет действовать оптимальным образом). По её просьбе санитар проверил содержимое ячеек и посчитал трупы. В представленном санитаром документе указано, сколько трупов какого типа лежат в ячейках подряд. Теперь Лизе Кадди осталось только написать соответствующую программу, для чего она решила нанять вас. Не желая раскрывать секрет своего розыгрыша (вдруг вы тоже поклонники Хауса), она формулирует для вас следующее задание.
Дана последовательность букв, в которой буквы всего трех типов: c, f, m. При этом для сокращения записи последовательность задана блоками одинаковых символов, идущих подряд. Требуется определить минимальное число перестановок букв, которое необходимо для упорядочивания последовательности по возрастанию кода буквы.
Входные данные
В первой строке одно натуральное число N (1 ≤ N ≤ 1000). Далее N строк, в каждой из которых описание блока: буква ('c', 'f' или 'm'), из которой состоит данный блок, и через пробел натуральное число K (1 ≤ K ≤ 1000) – размер блока.
Выходные данные
В первой строке одно число – требуемое минимальное количество перестановок.