540. Расстояние редактирования

Не решаласьЛёгкая

Даны строки s s и t t .

Найдите взвешенное расстояние редактирования (Расстояние Левенштейна) при стоимости вставки I I , удаления D D , замены S S .

Формат ввода

В первой строке два целых числа n n и m m ( 1 ≤ n , m ≤ 1000 1 \le n, m \le 1000 ), длины строк s s и t t соответственно.

Во второй строке дано s s , s s состоит из маленьких букв английского алфавита.

В третьей строке дано t t , t t состоит из маленьких букв английского алфавита.

В четвертой строке три целых числа I I , D D и S S ( 1 ≤ I , D , S ≤ 100 1 \le I, D, S \le 100 ).

Формат вывода

Выведите одно число — минимальную стоимость получения t t из s s с использованием операций вставки символа, удаления символа и замены символа на любой другой.

Ограничения

Ограничение времени
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

Теги

3.5.1
Нужно войти, чтобы отправить решение.Войти