Number lock 2

Time limit2sMemory limit512 MB

Summary

Given two equal-length digit strings S and T, find the fewest moves to turn S into T where a move shifts any contiguous block of dials one step up or down modulo 10.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Prefix sum, Implementation
Solved: No attempts yet

Problem

A number lock has N dials in a row. Each dial carries the digits 0 to 9 in order and shows one of them.

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

You may turn several dials at the same time. Dials turned together must be adjacent, and they all move one step in the same direction. There is no limit on how many you turn at once. One such turn counts as one move.

For example, if the lock shows 123, a single move produces 012 by turning every dial down, 234 by turning every dial up, 133 by turning the middle dial up, or 013 by turning the first two dials down. 224 cannot be reached in one move.

Given the current state S and the target state T, write a program that finds the smallest number of moves needed to turn S into T.

Input

The first line contains S and the second line contains T. The two strings have the same length, which is between 1 and 2500. Every character is a digit from 0 to 9, and a leading 0 is allowed.

Output

Print the smallest number of moves needed to turn 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
```