408736: GYM103286 A Рудольф и ОВД

A. Рудольф и ОВДограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Недавно Рудольф сдавал экзамен по Очень Важной Дисциплине, в котором был Самый Важный Вопрос. Ответом на вопрос может быть только строка из строчных латинских букв. Но Рудольфу не повезло, и он дал неверный ответ. Рудольф знает, что перед проверкой экзамена все ответы загружаются в базу данных, к которой у Рудольфа есть доступ.

Рудольфу доступны следующие команды:

• удалить символ из начала или с конца строки, данная команда занимает $$$2$$$ единицы времени;
• добавить символ в начало или в конец строки, данная команда занимает $$$2$$$ единицы времени;
• заменить любой символ строки на противоположный (например, «a» на «z», «b» на «y» и так далее), данная команда занимает $$$1$$$ единицу времени.

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

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

Первая строка содержит целые числа $$$N$$$ и $$$M$$$ ($$$1 \le N, M \le 3000$$$) — длина строки, являющейся ответом Рудольфа, и длина строки, являющейся верным ответом.

Вторая строка содержит последовательность $$$S_1$$$, состоящую из $$$N$$$ строчных латинских букв, — ответ, данный Рудольфом.

Третья строка содержит последовательность $$$S_2$$$, состоящую из $$$M$$$ строчных латинских букв — верный ответ.

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

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

ПримерыВходные данные

7 6
zabxdda
abcdxy

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

11

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

7 7
haransp
saransk

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

2

Примечание

В первом тесте мы можем получить ответ, удалив из строки один символ в начале («z») и два в конце («a» и «d»), заменив четвёртый символ («x» на «c»), и добавив в конец два символа («x» и «y»).