Minimum Edit Distance

You are given two strings. Your task is to compute the minimum number of operations required to convert the first string into the second string. The permitted operations are:

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

Each operation has a cost of 1.

Let \(dp[i][j]\) be the minimum number of operations required to convert the first \(i\) characters of the first string into the first \(j\) characters of the second string. The recurrence relation is given by:

\[ dp[i][j] = \begin{cases} i, & \text{if } j = 0,\\ j, & \text{if } i = 0,\\ dp[i-1][j-1], & \text{if } s1[i-1] = s2[j-1],\\ 1 + \min\{ dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1] \}, & \text{otherwise.} \]

Your solution should read the input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input consists of two lines. The first line contains the first string, and the second line contains the second string.

outputFormat

Output a single integer representing the minimum edit distance between the two strings.

## sample

horse
ros

3