Code Submission Evaluation System Login

CSES Problem Set

Edit Distance


Task | Statistics


CSES - Edit DistanceCSES - Edit Distance

Time limit:1.00 s Memory limit:512 MB

The edit distance between two strings is the minimum number of operations required to transform one string into the other.

The allowed operations are: For example, the edit distance between LOVE and MOVIE is 2, because you can first replace L with M, and then add I.

Your task is to calculate the edit distance between two strings.

Input

The first input line has a string that contains $n$ characters between A–Z.

The second input line has a string that contains $m$ characters between A–Z.

Output

Print one integer: the edit distance between the strings.

Constraints
Example

Input:
LOVE
MOVIE


Output:
2