Edit Distance Computation

This problem requires you to compute the minimum number of operations needed to convert one string into another. The allowed operations are:

• Insertion: Insert a character.
• Deletion: Remove a character.
• Replacement: Replace a character.

You are given two strings. Your task is to determine the minimum number of operations required to transform the first string into the second string.

This is a typical dynamic programming problem. The recurrence relation for this problem is:

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

Use this formula to guide your implementation.

inputFormat

The input is provided via stdin and consists of two lines.

• The first line contains the string s1.
• The second line contains the string s2.

Both strings may include lowercase and uppercase letters and can be empty.

outputFormat

The output should be printed to stdout as a single integer representing the minimum number of operations required to convert s1 into s2.

## sample

abcdef
azced

3

</p>