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

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

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

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

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

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

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

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