- Описание
- Решения
- Разборы
- Кодерун AI β
540. Расстояние редактирования
Даны строки и .
Найдите взвешенное расстояние редактирования (Расстояние Левенштейна) при стоимости вставки , удаления , замены .
Формат ввода
В первой строке два целых числа и ( ), длины строк и соответственно.
Во второй строке дано , состоит из маленьких букв английского алфавита.
В третьей строке дано , состоит из маленьких букв английского алфавита.
В четвертой строке три целых числа , и ( ).
Формат вывода
Выведите одно число — минимальную стоимость получения из с использованием операций вставки символа, удаления символа и замены символа на любой другой.
Ограничения
- Ограничение времени
- 2 с
- Ограничение памяти
- 512 МБ
Примеры
Пример 1
Ввод
7 11
coderun
competition
1 1 1
Вывод
7
Пример 2
Ввод
7 11
coderun
competition
1 1 100
Вывод
10
Пример 3
Ввод
7 11
coderun
competition
100 1 1
Вывод
403
Пример 4
Ввод
7 11
coderun
competition
1 100 1
Вывод
7