Над текстовим рядком можна виконувати наступні операції:

1. Замінити один символ рядка на будь-який інший символ.

2. Видалити довільний символ в рядку.

3. Вставити довільний символ в довільне місце в рядку.

Відстань Левенштайна (або редакційна відстань, Edit distance) - це найменша кількість таких операцій, за допомогою яких можна отримати з одого рядка інший.

Визначіть відстань Левенштайна для двух заданих рядків.

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

Два рядки довжиною не більше 1000 символів, що містять лише великі латинські літери

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

Єдине число - відстань Левенштайна між заданими двома рядками

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

ABCDEFGH
ACDEXGIH

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

3