Minimum Edit Distance

You are given two strings s and t, consisting of lowercase English letters. Your task is to compute the minimum edit distance between them, i.e. the minimum number of operations required to convert s into t.

The allowed operations are:

• Insertion of a single character,
• Deletion of a single character,
• Replacement of a single character.

This problem can be solved using dynamic programming. Let \(dp[i][j]\) denote the minimum edit distance between the first \(i\) characters of s and the first \(j\) characters of t. The recurrence is given by:

[ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1] & \text{if } s[i-1] = t[j-1], \ 1 + \min{\text{dp}[i-1][j],\text{dp}[i][j-1],\text{dp}[i-1][j-1]} & \text{if } s[i-1] \neq t[j-1]. \end{cases} ]

Compute and output the minimum number of operations required.

inputFormat

The input consists of exactly two lines from standard input (stdin):

• The first line contains the string s.
• The second line contains the string t.

Both strings contain only lowercase English letters and their lengths are between 0 and 1000 inclusive.

outputFormat

Output a single integer representing the minimum edit distance between s and t to standard output (stdout).

## sample

horse
ros

3