문자 메시지 입력 선수권

휴대전화 회사 Só Birutas Celulares는 해마다 문자 메시지 입력 선수권 대회를 연다. 주어진 메시지를 가장 빨리 입력한 사람이 우승한다.

대회에서 반드시 써야 하는 공식 단말기의 자판은 아주 단순하다. 자판은 3열 4행으로 다음과 같이 배치되어 있다.

1 2 3
4 5 6
7 8 9
* 0 #

엄지만으로 키를 눌러야 하므로 모든 키는 한 변이 1센티미터인 정사각형이고, 붙어 있는 두 키 사이에는 빈틈이 없다.

2번부터 9번까지의 키로 'a'부터 'z'까지의 글자를 입력한다. 방식은 보통 휴대전화와 같다. 한 키에 배정된 글자를 얻으려면 원하는 글자의 순서와 같은 횟수만큼 그 키를 누른다. 3번 키를 한 번 누르면 'd'가 되고, 다시 누르면 'e', 한 번 더 누르면 'f'가 된다. 계속 누르면 숫자 '3'이 나오고 그다음에는 다시 'd'로 돌아간다. 각 키에 배정된 글자는 2번이 'abc', 3번이 'def', 4번이 'ghi', 5번이 'jkl', 6번이 'mno', 7번이 'pqrs', 8번이 'tuv', 9번이 'wxyz'이다. 0번 키는 메시지에 공백을 넣는 데 쓰고, 1번 키와 * 키는 이 대회에서 쓰지 않는다.

메시지에서 같은 키로 만드는 글자가 연달아 나오면 # 키를 써야 한다. 이 키는 같은 키를 누르는 두 글자의 입력을 서로 끊어 준다. 예를 들어 "casa"를 입력하려면 2, 2, 2, #, 2, 7, 7, 7, 7, 2 순서로 키를 누른다.

올해는 주최 측이 대회를 더 흥미롭게 하려고 자유 낙하 중에 메시지를 입력하도록 정했다. 참가자는 휴대전화를 들고 비행기에서 뛰어내려 메시지를 입력하고, 메시지가 오류 없이 완성되면 컴퓨터 장치가 낙하산을 자동으로 펴 준다. 다만 이 규칙 때문에 어려움이 하나 늘었다. 낙하 중에 휴대전화를 놓치지 않으려면 한쪽 엄지로 단말기를 붙잡고 있어야 하고, 나머지 엄지로만 키를 누르거나 엄지를 움직일 수 있다. 즉 두 엄지 중 하나는 항상 고정되어 있다. 그래서 두 엄지가 동시에 움직이는 일은 없고, 전체 시간은 모든 이동 시간과 모든 키 누름 시간의 합이다.

관객의 호기심을 채우려고, 길이가 140자 이하인 메시지가 주어졌을 때 이상적인 참가자가 그 메시지를 입력하는 데 필요한 최소 시간을 구하는 프로그램을 만들어야 한다. 이상적인 참가자는 엄지를 초속 30센티미터로 움직이고, 키 하나를 누르는 데 0.2초가 걸리며, 자유 낙하를 시작할 때 왼쪽 엄지는 4번 키, 오른쪽 엄지는 6번 키 위에 있고, 언제나 키의 중심을 정확히 누른다.

입력은 테스트 케이스 여러 개로 이루어진다. 각 테스트 케이스는 메시지 한 개이고, 메시지는 'a'부터 'z'까지의 소문자와 공백으로만 이루어진 길이 1 이상 140 이하의 문자열이다. 메시지는 공백으로 시작하거나 끝나지 않고, 공백이 두 개 연달아 나오지도 않는다. 입력은 파일의 끝(EOF)에서 끝난다.

각 테스트 케이스마다 이상적인 참가자가 주어진 메시지를 입력하는 데 걸리는 최소 시간을 초 단위로 한 줄에 출력한다. 소수점 아래 두 자리까지 출력한다.