Descripción

Has estado reflexionando sobre cómo medir la distancia entre dos palabras y cómo podrían transformarse entre sí usando operaciones simples. Decidiste convertir este concepto en un problema de programación para desafiar tus habilidades y compartirlo con tus amigos.

La distancia entre dos cadenas es el número mínimo de operaciones necesarias para transformar una cadena en la otra. Las operaciones permitidas son:

• Añadir un carácter a la cadena.
• Eliminar un carácter de la cadena.
• Reemplazar un carácter en la cadena.

Por ejemplo, la edit distance entre las cadenas LOVE y MOVIE es 2, ya que puedes reemplazar L con M y luego añadir la letra I.

Problema

Dadas dos cadenas, determina la distancia entre ellas.

Entrada

La entrada consiste en dos líneas:

• La primera línea contiene una cadena \(A\) de longitud \(N\) (\(1 \leq N \leq 5000\)).
• La segunda línea contiene una cadena \(B\) de longitud \(M\) (\(1 \leq M \leq 5000\)).
• Ambas cadenas contienen solo caracteres en mayúsculas del alfabeto inglés (\(A-Z\)).

Salida

Imprime un único número entero que representa la distancia entre las dos cadenas.

Ejemplo

Entrada

LOVE
MOVIE

Salida

2