Minimum Edit Distance

You are given two strings, (word1) and (word2). Your task is to compute the minimum number of operations required to convert (word1) into (word2). The allowed operations are:

1. Insert a character
2. Delete a character
3. Replace a character

Each operation counts as one step. A classic approach to solve this problem is by using dynamic programming. In the DP solution, the state (dp[i][j]) represents the minimum number of operations required to convert the first (i) characters of (word1) to the first (j) characters of (word2).

inputFormat

The input consists of two lines from standard input. The first line contains the string (word1) and the second line contains the string (word2). Either string can be empty.

outputFormat

Output a single integer representing the minimum number of operations required to convert (word1) into (word2). The result should be printed to the standard output.## sample

horse
ros

3