ZOAC 3

Interview

Time limit1sMemory limit1024 MB

Summary

Two fingers start on given keys of a QWERTY keyboard; consonants are typed by the left finger and vowels by the right, and moving a finger costs Manhattan distance. Find the minimum total time to type the string.

Level: Medium5 of 10
Topics: Dynamic programming, Implementation, Math
Solved: No attempts yet

Problem

In December 2020, Seongwu is in charge of the opening of the third ZOAC, and he wants to spread the word about ZOAC faster than anyone else.

Unfortunately, Seongwu types with the eagle method!

The eagle method means typing with only the index fingers of both hands.
Seongwu types the Korean consonant keys with his left index finger and the Korean vowel keys with his right index finger.
When the coordinates of a are (x1, y1) and the coordinates of b are (x2, y2), moving Seongwu's finger from a to b takes the taxi distance between a and b, |x1-x2|+|y1-y2|.
Pressing each key takes 1 unit of time.
Seongwu cannot move both hands at the same time.
The keyboard Seongwu uses is a QWERTY keyboard and looks like the picture below.

For the busy Seongwu, find the minimum time needed to type the given string.

Input

The first line gives two lowercase alphabet letters sL and sR. sL and sR are the starting positions of the left index finger and the right index finger, respectively.

The next line gives a string of lowercase alphabet letters. The length of the string is at most 100. The string is not empty.

Output

Print the minimum time needed to type the string given as input.

Hint

The reason Seongwu cannot move both hands at the same time is as follows.

A person cannot do two or more things at the same time.
A graduate student is a person.
Seongwu is a graduate student.

Examples1

Example 1
Input
```
z o
zoac
```
Expected output
```
8
```