Edit Distance

Given two strings, word1 and word2, determine the minimum number of operations required to convert word1 into word2. You can perform the following operations:

• Insert a character
• Delete a character
• Replace a character

This problem can be solved using dynamic programming. The cost function is given by the recurrence relation:

$$

dp[i][j]=\begin{cases} i, & \text{if }j = 0\ j, & \text{if }i = 0\ dp[i-1][j-1], & \text{if }word1[i-1]=word2[j-1]\ \min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1, & \text{otherwise} \end{cases}

$$

Your task is to compute the value of dp[m][n], where m and n are the lengths of word1 and word2 respectively.

## inputFormat

The input consists of two lines:

1. The first line contains the string word1.
2. The second line contains the string word2.

Both strings may include only standard ASCII characters.

## outputFormat

Output a single integer that represents the minimum number of operations required to convert word1 into word2.

## sample

horse
ros

3

$$