Hide

# ReMorse

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 just

THEQUICKBROWNDOGJUMPSOVERTHELAZYFOX

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 32\, 000$) 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.

Sample Input 1 Sample Output 1
ICPC

17

Sample Input 2 Sample Output 2
A

1

Sample Input 3 Sample Output 3
The quick brown dog jumps over the lazy fox.

335

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 2.2easy
Statistics Show