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