Morse Code is an assignment of sequences of dots and dashes to alphabet characters. You are to create a Morse-like code that yields the shortest total length to a given message, and return that total length.

A dot symbol has length $1$. A dash symbol has length $3$. The gap between symbols within a character encoding has length $1$. The gap between character encodings has length $3$. Spaces, punctuation, and alphabetic case are ignored, so the text:The quick brown dog jumps over the lazy fox.

is encoded as though it were justTHEQUICKBROWNDOGJUMPSOVERTHELAZYFOX

For example, with input ICPC, the answer is $17$: Encode the C’s with a single dot, the I with a dash, and the P with two dots, for an encoding of— $\bullet $ $\bullet \bullet $ $\bullet $

which has length$(3)+3+(1)+3+(1+1+1)+3+(1) = 17$. 

-----Input-----
The single line of input contains a string $s$ ($1 \le |s| \le 32000$) of upper-case or lower-case letters, spaces, commas, periods, exclamation points, and/or question marks. Everything but the letters should be ignored. The line will contain at least one letter.

-----Output-----
Output a single integer, which is the length of $s$ when encoded with an optimal reassignment of the sequences of Morse Code.

-----Examples-----
Sample Input 1:
ICPC
Sample Output 1:
17

Sample Input 2:
A
Sample Output 2:
1

Source: kattis | Difficulty: MEDIUM


Solutions: