K. Правки разной цены

Те же три операции над строкой — вставка, удаление, замена, — но теперь они стоят по-разному: вставка стоит $p$, удаление $q$, замена $r$.

Найдите наименьшую суммарную стоимость правок, превращающих первую строку во вторую.

Формула перехода почти та же, что у обычного расстояния. Внимательнее с базой: она перестаёт быть просто номером строки.

Первая строка содержит три натуральных числа $p$, $q$, $r$, не превосходящих 100.

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

Одно число — наименьшая стоимость.