Відстань редагування між двома рядками — це мінімальна кількість операцій, необхідних для перетворення одного рядка в інший.

Дозволені операції:

• Додайте один символ до рядка.
• Видалити один символ із рядка.
• Замінити один символ у рядку.

Наприклад, відстань редагування між LOVE і MOVIE дорівнює 2, тому що ви можете спочатку замінити L на M, а потім додати I.

Ваше завдання — обчислити відстань редагування між двома рядками.

Обмеження

• ~1 \le n,m \le 5000~

Формат вхідних даних

Перший рядок введення містить рядок із ~n~ символів між A–Z.

Другий вхідний рядок містить рядок із ~m~ символів між A–Z.

Формат вихідних даних

Вивести одне ціле число: редагована відстань між рядками.

Приклад вхідних даних

LOVE
MOVIE

Приклад вихідних даних

2