Недавно Рудольф сдавал экзамен по Очень Важной Дисциплине, в котором был Самый Важный Вопрос. Ответом на вопрос может быть только строка из строчных латинских букв. Но Рудольфу не повезло, и он дал неверный ответ. Рудольф знает, что перед проверкой экзамена все ответы загружаются в базу данных, к которой у Рудольфа есть доступ.
Рудольфу доступны следующие команды:
Рудольф боится не сдать экзамен и хочет успеть исправить ответ до того, как преподаватель будет проверять его, поэтому он хочет исправить ответ на правильный как можно быстрее. Помогите Рудольфу сделать это.
Первая строка содержит целые числа $$$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»).
