Doctor House in the Morgue
Dr. House, the protagonist of the popular TV series, has once again played a prank on his boss, Dr. Cuddy. In response, she plans to prank him back by sending him to the morgue to organize the corpses in numbered slots. The corpses are categorized into three types: male (denoted by m), female (f), and child (c). Dr. House's task is to arrange all the child corpses first, followed by the female corpses, and finally the male corpses.
It's important to note that Dr. House has a disability affecting his leg, making it challenging for him to move corpses, even with stretchers. Therefore, the considerate Dr. Cuddy wants to determine the minimum number of corpse relocations he would need to make, assuming he acts optimally. To assist her, an orderly has already checked the slots and counted the corpses. The orderly's report specifies how many corpses of each type are in consecutive slots. Dr. Cuddy now needs to write a program to calculate this, and she has enlisted your help. To keep her prank a secret (in case you're also fans of House), she presents the task as follows:
You are given a sequence of letters, each representing one of three types: c, f, or m. For simplicity, the sequence is provided in blocks of consecutive identical symbols. Your goal is to determine the minimum number of swaps required to sort the sequence in ascending order based on the letter code.
Input
The first line contains a single natural number N (1 ≤ N ≤ 1000). This is followed by N lines, each describing a block: a letter ('c', 'f', or 'm'), followed by a space and a natural number K (1 ≤ K ≤ 1000) – the size of the block.
Output
The output should be a single number representing the minimum number of swaps needed.