Number Lock

Interview

Time limit2sMemory limit512 MB

Summary

Given two equal-length digit strings S and T, find the minimum number of turns where each turn adds 1 or subtracts 1 (mod 10) to every dial in some contiguous range.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Implementation, Array
Solved: No attempts yet

Problem

A number lock has $N$ dials. Each dial carries the digits 0 through 9 in order.

Turning a dial up changes the visible digit from 0 to 1, from 1 to 2, and so on, with 9 changing back to 0. Turning a dial down moves in the opposite direction.

You can turn several dials at once. The dials turned together must be consecutive, and there is no limit on how many. Every dial turned together moves one step in the same direction.

For example, if the lock reads 123, you can turn all three dials down to get 012, turn all three up to get 234, turn only the middle dial up to get 133, or turn the first two dials down to get 013. You cannot reach 224 with a single turn.

Given the current state $S$ and the target state $T$ , write a program that finds the minimum number of turns needed to change $S$ into $T$ .

Input

The first line contains $S$ . The second line contains $T$ . The two strings have the same length $N$ , and $1 \le N \le 50$ . Both consist only of the digits 0 through 9, and either one may start with 0.

Output

Print the minimum number of turns needed to change $S$ into $T$ .

Examples5

Example 1
Input
```
123
112
```
Expected output
```
1
```
Example 2
Input
```
1
7
```
Expected output
```
4
```
Example 3
Input
```
607
607
```
Expected output
```
0
```
Example 4
Input
```
1234
4567
```
Expected output
```
3
```
Example 5
Input
```
020
909
```
Expected output
```
2
```