La distancia de edición entre dos cadenas es el número mínimo de operaciones requeridas para transformar una cadena en la otra.

Las operaciones permitidas son:

• Agregar un carácter a la cadena.
• Eliminar un carácter de la cadena.
• Reemplazar un carácter en la cadena.

Por ejemplo, la distancia de edición entre LOVE y MOVIE es 2, porque primero puedes reemplazar L con M, y luego agregar I.

Tu tarea es calcular la distancia de edición entre dos cadenas.

Entrada

La primera línea de entrada tiene una cadena que contiene \(N\) (\(1 \leq N \leq 5000\))caracteres entre A–Z.

La segunda línea de entrada tiene una cadena que contiene \(M\) (\(1 \leq M \leq 5000\)) caracteres entre A–Z.

Salida

Imprime un número entero: la distancia de edición entre las cadenas.

Ejemplo

Entrada:

LOVE
MOVIE

Salida:

2