Minimum edit

Compute the Levenshtein distance between two lowercase strings, using the fewest insert, delete, and replace operations to change A into B.

Medium6Dynamic programmingStringArrayPrefix sumInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples10

Problem

Given two strings $A$ and $B$ , the task of turning $A$ into $B$ with the fewest operations is called the minimum edit problem.

Three operations apply to $A$ .

Insert: put one character at any position of $A$ .
Delete: remove one character of $A$ .
Replace: change one character of $A$ into another character.

Given the two strings, write a program that computes the minimum number of edits.

Input

The first line has the string $A$ and the second line has the string $B$ . Both strings consist of lowercase letters only, and neither is longer than 1000 characters.

Output

Print on the first line the minimum number of edits that turn $A$ into $B$ .