G. Расстояние Левенштейна
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

  • замена: стоимость замены одного символа на другой равна разности порядковых номеров этих символов в алфавите.
  • вставка/удаление: стоимость вставки символа в строку или удаления символа из строки равна порядковому номеру этого символа в алфавите (см. примеры).

Вам даны две строки. Найдите расстояние Левенштейна между ними.

Входные данные

Входные данные состоят из двух строк; в каждой строке записана последовательность строчных латинских символов длины от 1 до 100, включительно.

Выходные данные

Выведите одно число — расстояние Левенштейна между этими строками.

Примеры
Входные данные
arc
bug
Выходные данные
8
Входные данные
dome
drone
Выходные данные
19
Примечание

В первом примере следует заменить a на b (стоимость 1), r на u (стоимость 3) и c на g (стоимость 4).

Во втором примере следует вставить r (стоимость 18) и заменить m на n (стоимость 1).