Minimum turns on the number screws

Interview

Time limit1sMemory limit128 MB

Summary

Each left turn on a screw also rotates every screw below it; find the fewest total notches to reach the wanted digit string.

Level: Medium6 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

$N$ number screws are connected one above another. The screw at the top is screw 1 and the screw at the bottom is screw $N$ . Every screw has 10 faces, and the digits 0, 1, 2, 3, …, 9 are written on them one at a time, in order, going to the right.

Turning one screw a single notch to the left also turns every screw below it by one notch. Turning a screw to the right moves that screw alone, and the screws below stay where they are. A screw that moved one notch to the left shows a digit larger by 1, and 0 follows 9. A screw that moved one notch to the right shows a digit smaller by 1, and 9 follows 0.

Read the digits from the front, top to bottom. You are given the current state and the wanted state. Write a program that finds the smallest total number of notches needed to turn the current state into the wanted state. The turns themselves are not printed.

For example, with three screws, a current state of 326 and a wanted state of 446, the smallest total is 4 notches. Turning screw 1 one notch to the left gives 437, turning screw 2 one notch to the left gives 448, and turning screw 3 two notches to the right gives 446.

Input

The first line contains the number of screws $N$ . The second line contains the current state and the third line contains the wanted state. Each of those two lines is a string of $N$ digits from 0 to 9, and it may start with 0. $N$ is between 3 and 10,000.

Output

Print the smallest total number of notches needed to turn the current state into the wanted state.

Examples4

Example 1
Input
```
3
326
446
```
Expected output
```
4
```
Example 2
Input
```
3
326
326
```
Expected output
```
0
```
Example 3
Input
```
3
999
000
```
Expected output
```
1
```
Example 4
Input
```
3
655
045
```
Expected output
```
7
```