18008번 - ReMorse 다국어

문제

Morse code is an assignment of sequences of dot and dash symbols to alphabet characters. You are to reassign the sequences of Morse code so that it 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

THEQUICKBROWNDOGJUMPSOVERTHELAZYFOX

For instance, for the input ICPC, the answer is 17. Encode the Cs with a single dot, the I with a dash, and the P with two dots, for an encoding of

− ∙ ∙∙ ∙

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

입력

The single line of input consists of a string s (1 ≤ |s| ≤ 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 a single integer, which is the length of s when encoded with an optimal reassignment of the sequences of Morse code.

제한

힌트