Dial Lock

Time limit2sMemory limit128 MB

Summary

Given a current dial state and a password of N digits, find the minimum number of operations, each rotating a contiguous block of at most three circular dials by 1 to 3 steps, to reach the password.

Level: Medium7 of 10
Topics: Dynamic programming, Math, Greedy, Array
Solved: No attempts yet

Problem

A laptop is protected with a dial lock. The lock consists of $N$ circular disks. Each disk shows one digit from 0 to 9, and because each disk is circular, 0 and 9 are adjacent.

In one operation, choose a non-empty contiguous block of at most three disks. Rotate every chosen disk in the same direction by the same number of steps, where the number of steps is between 1 and 3. The direction may be clockwise or counterclockwise.

Given the current state of the lock and the password, find the minimum number of operations needed to open the lock.

For the state 555 and password 464, rotating each disk separately would take 3 operations. Instead, rotate all three disks one step counterclockwise to make 444, then rotate the second disk two steps clockwise to make 464, for a total of 2 operations.

Input

The first line contains $N$ , the length of the password and the number of disks in the lock. $N$ is a positive integer at most 100.

The second line contains the current state of the lock, and the third line contains the password. Both strings have length $N$ and consist only of digits from 0 to 9.

Output

Print the minimum number of operations needed to open the lock.

Examples4

Example 1
Input
```
3
555
464
```
Expected output
```
2
```
Example 2
Input
```
4
1234
3456
```
Expected output
```
2
```
Example 3
Input
```
8
06012005
06012005
```
Expected output
```
0
```
Example 4
Input
```
9
123456789
567412490
```
Expected output
```
5
```