## Problem Description

The Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965.

Given lowercase strings A and B, find the Levenshtein distance between A and B.

## Input

The first line of input will contain a string A

The second line of input will contain a string B

## Output

The output should contain one integer representing the Levenshtein distance.

## Limits

Let N and M be length of A and B respectively.

Subtask 1 (27%): 1 ≤ N, M ≤ 10

Subtask 2 (73%): 1 ≤ N, M ≤ 3 000

```abc
bcd```

`2`

## Explanation

Delete 'a', insert 'd'.

## Sample Input 2

```saturday
sunday```

`3`

## Explanation

Replace 'n' with 'r', insert âtâ, insert âaâ.

### Submitting .cpp to 'levenshtein'

Time Limit: 1 Seconds
Memory Limit: 256MB