Minimum Edit Distance

Given two strings s and t, your task is to compute 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 is a classic example of dynamic programming. One common recurrence used is given in LaTeX as:

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

Where dp[i][j] represents the minimum operations needed to convert the first i characters of s to the first j characters of t.

Note: The input will be given via standard input and the output should be produced on standard output.

inputFormat

The input consists of two lines:

1. The first line contains the string s.
2. The second line contains the string t.

Both strings can be empty.

outputFormat

Output a single integer representing the minimum number of operations required to convert string s to string t.

## sample

abc
yabd

2