Problem O
WordSpin
Žofka invented a new word puzzle. She gives you two strings $s_1$ and $s_2$ of the same length. You need to modify $s_1$ into $s_2$ as quickly as possible. The trick is that you are allowed to modify the strings only using the following types of moves: (1) shift forward where you choose a substring of one of the strings and shift each of its letters by 1 forward in the alphabet, or (2) shift backward where you shift each letter in a substring backward in the alphabet. The first move is not allowed if the substring contains the letter z while the second move is not allowed if the subtring contains a. What is the smallest number of moves you need to modify $s_1$ into $s_2$?
Input
Each word puzzle is described on a single line that contains the strings $s_1$ and $s_2$ separated by space. The strings contain only lower case letters. You may also assume that the length of each string is at most $10\, 000\, 000$.
Output
Output one line with the smallest number of moves needed to modify $s_1$ into $s_2$.
Note
The first sample input can be modified in the following way. First shift lo forward, getting helmp. Then shift h forward 12 times, getting telmp. Then shift l 11 times backward to get teamp and then shift p forward three times to get teams. Total number of moves is $1+12+11+3=27$.
The second sample input can be modified as follows. First shift the entire string forward, getting bbdddbbbb. Then shift ddd backward twice to get bbbbbbbbb. This requires 1+2=3 moves.
| Sample Input 1 | Sample Output 1 |
|---|---|
hello teams |
27 |
| Sample Input 2 | Sample Output 2 |
|---|---|
aacccaaaa bbbbbbbbb |
3 |
