Leave Your Name

Time limit12sMemory limit128 MB

Summary

Enter the given uppercase name with the fewest presses of letter-change, cursor-move, and insert buttons.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Shortest path
Solved: No attempts yet

Problem

Kkung just set the high score on a favorite game! Only the name is left to enter, and the entry pad makes that a chore.

The only characters available are the $26$ uppercase letters A to Z. No digits, no spaces, no lowercase letters, nothing else.
UP and DOWN change the letter you are about to enter. That letter starts at A, DOWN from A gives Z, and UP from Z gives A.
LEFT and RIGHT move the cursor by one slot. Once the cursor sits at one end, it cannot move further in that direction.
FIRE inserts the letter you are about to enter at the cursor. Whatever stood to the right shifts one slot over, and the cursor lands right after the inserted letter.

Say the name is 'ALMA'. Kkung can enter it like this.

Action	Presses	Name so far (\| = cursor)	Letter to enter
FIRE	1	A\|	A
UP	11	A\|	L
FIRE	1	AL\|	L
UP	1	AL\|	M
FIRE	1	ALM\|	M
DOWN	12	ALM\|	A
FIRE	1	ALMA\|	A

That costs $28$ presses. Now look at this run instead.

Action	Presses	Name so far (\| = cursor)	Letter to enter
FIRE	1	A\|	A
FIRE	1	AA\|	A
LEFT	1	A\|A	A
UP	11	A\|A	L
FIRE	1	AL\|A	L
UP	1	AL\|A	M
FIRE	1	ALM\|A	M

That finishes the same name in $17$ presses. Given a name, how few button presses are enough to enter it? The letter to enter starts at A, and the cursor may sit anywhere once the name is complete.

Input

Each test case is one line holding a name made only of uppercase letters, with length between $1$ and $18$ . The last line of the input holds a single 0.

Output

For each test case, print the smallest number of button presses that enters the name, one per line.

Examples1

Example 1
Input
```
ALMA
YES
0
```
Expected output
```
17
21
```