Cell-Phone Messaging

Ο Joe Coder μόλις έλαβε ένα κινητό τηλέφωνο για τα γενέθλιά του. Στην αρχή δεν ήταν τόσο ενθουσιασμένος με αυτό, αφού δεν του αρέσει να μιλάει τόσο πολύ, ούτε να ακούει για αυτό το θέμα, και απεχθάνεται να τον διακόπτουν τηλεφωνήματα ενώ γράφει κώδικα ή παίζει το αγαπημένο του παιχνίδι στον υπολογιστή. Όμως, ο Joe έμαθε ότι μπορεί να μιλήσει με τους φίλους του και επίσης να στείλει e-mail. Αυτό έκανε το τηλέφωνο πιο cool.

Για να χωρέσουν τα ~26~ γράμματα της αλφαβήτου στα πλήκτρα ενός κινητού τηλεφώνου, αντιστοιχίζονται πολλά γράμματα σε κάθε πλήκτρο, όπως φαίνεται στο σχέδιο. Για να γράψουμε ένα μήνυμα κειμένου, πρέπει να επιλέξουμε ένα γράμμα από ένα σύνολο που έχει εκχωρηθεί σε ένα κλειδί. Το πρώτο γράμμα σε ένα πλήκτρο επιλέγεται πατώντας το πλήκτρο μία φορά, το δεύτερο γράμμα πατώντας το πλήκτρο δύο φορές, το τρίτο γράμμα πατώντας το πλήκτρο τρεις φορές και ούτω καθεξής.

Για παράδειγμα, για να γράψουμε το "~a~" πατάμε το πλήκτρο "~2~" μία φορά και τελειώσαμε. Για να γράψουμε "~dada~" πατάμε ~3232~ —τέσσερα πατήματα πλήκτρων και για να γράψουμε "~bob~" πατάμε ~2266622~. Ένα προφανές θέμα είναι πώς γράφουμε δύο συνεχόμενα γράμματα στο ίδιο κλειδί, για παράδειγμα "~abba~" ή "~cell~". Το πρόβλημα επιλύεται με την εισαγωγή μιας δυνατότητας χρονικού ορίου: ένα γράμμα που εμφανίζεται αυτήν τη στιγμή επιλέγεται όταν πατηθεί ένα άλλο πλήκτρο, αλλά και μετά από μια παύση, δηλαδή ένα χρονικό όριο. Για παράδειγμα, για να γράψουμε "~abba~" πατάμε ~2~-pause-~22~-pause-~22~-pause-~2~. Για να γράψουμε "~cell~" πατάμε ~22233555~-pause-~555~ ή για να γράψουμε "~www~" πατάμε ~9~-pause-~9~-pause-~9~.

Αυτό το είδος πληκτρολόγησης απαιτεί λίγο χρόνο και ο Joe εργάζεται σε ένα πρόγραμμα για να υπολογίσει πόσο χρόνο χρειάζεται για να πληκτρολογήσετε ορισμένες λέξεις. Η υπόθεση του είναι ότι ξοδεύει ένα δευτερόλεπτο ανά πάτημα, και όποτε κάνει μια παύση χάνει άλλα δύο δευτερόλεπτα. Πρέπει να τον βοηθήσετε να υπολογίσει τον ελάχιστο χρόνο που χρειάζεται για να πληκτρολογήσει ένα μήνυμα, σύμφωνα με τις παραπάνω υποθέσεις.

Είσοδος

Κάθε γραμμή εισόδου περιέχει μια λέξη που αποτελείται μόνο από πεζά γράμματα. Οι λέξεις έχουν το πολύ ~20~ χαρακτήρες. Η είσοδος θα δοθεί από το πληκτρολόγιο και το πρόγραμμα θα πρέπει να σταματήσει να διαβάζει την είσοδο όταν έχει εισαχθεί η λέξη "halt" (διακοπή).

Έξοδος

Για κάθε λέξη εισόδου (εξαιρουμένης της λέξης halt), εκτυπώστε (στην οθόνη) τον ελάχιστο αριθμό δευτερολέπτων που απαιτούνται για την πληκτρολόγηση της λέξης, με έναν αριθμό εξόδου ανά γραμμή.

Παράδειγμα

input

a
dada
bob
abba
cell
www
halt

output

1
4
7
12
13
7