Minimum Edit Distance Transformation

You are given two strings: start and target. Your task is to compute the minimum number of operations required to transform start into target using the following three operations:

• Insertion: Insert a single character.
• Deletion: Delete a single character.
• Substitution: Replace one character with another.

This problem can be mathematically described using the edit distance defined by the recurrence:

$$dp[i][j]=\begin{cases}i, & j=0\\ j, & i=0\\ dp[i-1][j-1], & \text{if } start[i-1]=target[j-1] \\ 1+\min\{dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]\}, & \text{otherwise} \end{cases}$$

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

inputFormat

The input consists of two lines:

1. The first line contains the string start.
2. The second line contains the string target.

Both strings can be empty.

outputFormat

Output a single integer representing the minimum number of operations required to transform start into target.

## sample

kitten
sitting

3