410007: GYM103896 I Tyrannosaurus Typing

Terry the T-Rex loves typing! The only problem is that his extremely short arms severely limit his typing speed.

Terry has a message that he would like to send to his friend Perry the Pterodactyl. His message consists of a series of lowercase English letters and spaces (no punctuation, etc.).

Terry employs the classic hunt-and-peck method of typing: his index claws initially rest upon any key(s) that Terry chooses, and then for each letter in the message, Terry may move either of his index claws to the desired key and press it.

Terry's keyboard layout is shown above (though we only care about the lowercase English letters). Any spaces in the message may be ignored, as Terry will simply use his head to bash the space bar instead of bothering to use his claws. Otherwise, for each letter that Terry types, there is a cost associated with moving his claw from an old position to a new one.

The cost of moving a claw is equal to the Manhattan distance between the two keys (assuming that the keys are organized in a grid as shown above). Note that there is no additional cost associated with actually pressing a key.

Terry would like to know: based on his initial choice of claw positions and which claw he chooses to use to type each letter of the message, what is the minimum cost to send his message to Perry?

The input will consist of a single line $$$S$$$, containing Terry's message to Perry ($$$1 \leq |S| \leq 10^5$$$). The message will consist of lowercase English letters and spaces, and there will be no extraneous spaces (i.e. the message will not begin or end in a space and there will never be more than one space in a row).

Output should consist of a single integer, the minimum cost for Terry to send his message to Perry.

hello world

10

qpw

1