K. Расстояние по Левенштейну

Со строкой разрешены три операции: заменить один символ на другой, удалить один символ, вставить символ в произвольное место.

Наименьшее число таких операций, превращающих одну строку в другую, называется расстоянием Левенштейна. Найдите его для двух данных строк.

Две строки, каждая длиной от 1 до 1000, состоящие только из заглавных латинских букв.

Одно число — расстояние Левенштейна.