Problem C

Worse Code

Morse code has been used for a long time in telecommunications. Its external representation consists of sequences of two distinct atomic symbols: the ``dot'' (a short tone) and the ``dash'' (a slightly longer tone). A sequence of dots and dashes forms a symbol.

The exact representation associated with each symbol was constructed after a statistical analysis of the occurrence of the various letters in English text, so as to give to the most frequent letters the shortest representation. For instance, the letter E is represented as a single dot while the letter T is a single dash. In regular morse code, symbols are separated by a small pause (the space atomic symbol).

Problem

The technology you are employing does not allow for spaces to separate symbols, so different arrangements have to be made: you'll have to make do with a Worse Code, in which there may be only two distinct symbols (the dot and the dash).

You are asked to write a program that evaluates the resourses necessary to transmit a particular sentence in Worse Code. In order to do that, your program has to be able to produce the optimal Worse code, tailored for the input sentence.

The problem can be formulated as follows:

• With just an input sentence, to (internally) determine an optimal Worse Code for that sentence and display the length (in number of ``dash-dot'' atomic symbols) of the resulting coded message.

Input

Several input sentences, each sentence in one or more lines and terminated with a blank line or the end-of-file character.

Notes:

• Sequences of whitespace and newlines within a sentence are to be converted into a single space character, except if they are at the end of the sentence, in which case they are ignored.
• Lower case letters are mapped to the corresponding upper case equivalents. Any other characters, including accented letters, are simply ignored.

Output

The number of atomic symbols (dot or dash) in the optimal Worse Code representation for each input sentence on a line by itself.

Sample Input

THE QUICK BROWN FOX JUMPS
OVER THE LAZY DOG.

Don't make codes for letters not appearing
in the text!

Sample Output

192
204

MIUP'2002: 2nd. Portuguese National ACM Programming Contest