Under construction

Still being built. Things may change

Make a Number

Time limit1.5sMemory limit1024 MB

Summary
Find the minimum cost to turn A into B using single-digit changes (cost is the digit gap) or adding an integer y (cost |y|).
Level

Medium6 of 10

Topics
Shortest path, Dynamic programming, Implementation
Solved
No attempts yet

Problem

Two positive integers A,BA, B are given.

You may apply the following two operations to AA in any order and any number of times.

  1. Let the decimal representation of AA be dk−1⋯d0d_{k-1} \cdots d_0. That is, A=∑i=0k−1di⋅10iA = \sum_{i=0}^{k-1} d_i \cdot 10^i, where each did_i is an integer with 0≤di≤90 \le d_i \le 9, and dk−1≠0d_{k-1} \ne 0. Choose any integer ii (0≤i<k0 \le i < k) and any xx (0≤x≤90 \le x \le 9), and replace did_i with xx. If i=k−1i = k-1, then 0<x≤90 < x \le 9 must hold. The cost of this operation is ∣x−di∣|x - d_i|.
  2. Choose any integer yy with y>−Ay > -A and add it to AA. The cost of this operation is ∣y∣|y|.

For example, choosing i=1i=1 and x=7x=7 for the number 2024 and performing operation 1 once gives 2074. The cost of this operation is ∣7−2∣=5|7-2| = 5.

However, choosing i=3i=3 and x=0x=0 to get 0024, or choosing i=4i=4 and x=1x=1 to get 12024, is not allowed because it violates the conditions.

Also, choosing y=−926y=-926 for the number 926 and performing operation 2 twice to get 0 is not allowed either.

What is the minimum total cost of turning AA into BB?

Input

The first line contains two positive integers A,BA, B (1≤A,B<5 000 0001 \le A, B < 5\,000\,000), separated by a space.

Output

Print the minimum total cost of turning AA into BB.

Examples2

  1. Example 1

    Input
    1273 29856
    
    Expected output
    33
    
  2. Example 2

    Input
    2024926 2024926
    
    Expected output
    0