B. Ловя мошенников
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две строки $$$A$$$ и $$$B$$$, представляющие эссе двух учеников, которые подозреваются в мошенничестве. Для любых двух строк $$$C$$$, $$$D$$$ мы определяем оценку их сходства $$$S(C,D)$$$ как $$$4\cdot LCS(C,D) - |C| - |D|$$$, где $$$LCS(C,D)$$$ обозначает длину наибольшей общей подпоследовательности строк $$$C$$$ и $$$D$$$.

Вы считаете, что могла быть скопирована только часть эссе, поэтому вас интересуют их подстроки.

Вычислите максимальную оценку сходства по всем парам подстрок. Более формально, выведите максимальное значение $$$S(C, D)$$$, по всем парам $$$(C, D)$$$, где $$$C$$$ — некоторая подстрока $$$A$$$, а $$$D$$$ — некоторая подстрока $$$B$$$.

Если $$$X$$$ — строка, то $$$|X|$$$ обозначает ее длину.

Строка $$$a$$$ является подстрокой строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

Строка $$$a$$$ является подпоследовательностью строки $$$b$$$, если $$$a$$$ можно получить из $$$b$$$ путем удаления нескольких (возможно, нуля или всех) символов.

Обратите внимание на разницу между подстрокой и подпоследовательностью, так как оба термина встречаются в условии задачи.

Возможно, вам будет интересно прочитать страницу Википедии о наибольшей общей подпоследовательности.

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

Первая строка содержит два положительных целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 5000$$$) — длины двух строк $$$A$$$ и $$$B$$$.

Вторая строка содержит строку, состоящую из $$$n$$$ строчных латинских букв — строку $$$A$$$.

В третьей строке находится строка, состоящая из $$$m$$$ строчных латинских букв  — строку $$$B$$$.

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

Выведите максимальное значение $$$S(C, D)$$$, по всем парам $$$(C, D)$$$, где $$$C$$$ — некоторая подстрока $$$A$$$, а $$$D$$$ — некоторая подстрока $$$B$$$.

Примеры
Входные данные
4 5
abba
babab
Выходные данные
5
Входные данные
8 10
bbbbabab
bbbabaaaaa
Выходные данные
12
Входные данные
7 7
uiibwws
qhtkxcn
Выходные данные
0
Примечание

В первом примере:

abb из первой строки и abab из второй строки имеют LCS равный abb.

Результат равен $$$S(abb, abab) = (4 \cdot |abb|$$$) - $$$|abb|$$$ - $$$|abab|$$$ = $$$4 \cdot 3 - 3 - 4 = 5$$$.