Minimum Edit Distance

You are given two strings, s and t. Your task is to determine the minimum number of operations required to transform s into t. The allowed operations are:

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

Each operation counts as one step. Formally, if we define dp[i][j] as the minimum number of operations required to transform the first i characters of s into the first j characters of t, then the state transition is given by:

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

For example, transforming "horse" into "ros" requires 3 operations.

inputFormat

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

Both strings can be empty.

outputFormat

Output a single integer --- the minimum number of edit operations required to transform s into t.

## sample

horse
ros

3