Условие задачи

В Королевстве IOI недавно проложили новую железную дорогу. Поезд, курсирующий по железной дороге Королевства IOI, состоит из нескольких сцепленных друг с другом вагонов, причём вагоны бывают $2$ типов: I и O. Каждый вагон можно сцеплять только с вагоном другого типа. Кроме того, поскольку на обоих концах поезда должны располагаться кабины машиниста, крайние вагоны с обоих концов поезда должны быть типа I. Поезд представляется строкой, полученной последовательным соединением символов, обозначающих типы его вагонов, а длиной поезда считается длина этой строки. Например, сцепив вагоны в порядке IOIOI, можно сформировать поезд длины $5$, а один вагон I сам по себе образует поезд длины $1$. Если же расположить вагоны в порядке вроде OIOI или IOOI, сформировать поезд нельзя.

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

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

При формировании поезда не обязательно использовать все вагоны, находящиеся в депо. Иными словами, после завершения формирования поезда в депо могут остаться неиспользованные вагоны.

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

Рисунок: В процессе формирования поезда (сверху: путь ожидания; снизу слева: формируемый поезд; справа: депо S и депо T); в этот момент переводить вагоны из депо на путь ожидания нельзя. Этот рисунок соответствует Примеру 1.

Задача

По заданной информации о вагонах, находящихся в депо, напишите программу, определяющую максимально возможную длину поезда, который можно сформировать. Ряд вагонов в каждом депо задаётся строкой, состоящей только из символов $2$ типов — I и O, причём информация о $2$ депо даётся соответственно в виде строки $S$ длины $M$ и строки $T$ длины $N$. Каждый символ обозначает $1$ вагон и совпадает с типом этого вагона. $1$-й символ строки обозначает вагон, ближайший к выходу из депо, а последний символ — вагон, находящийся в самом конце депо.

Ограничения

• $1 \le M \le 2\,000$: длина строки $S$.
• $1 \le N \le 2\,000$: длина строки $T$.

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

Считайте следующие данные из стандартного потока ввода.

• В $1$-й строке через пробел записаны числа $M, N$.
• Во $2$-й строке записана строка $S$.
• В $3$-й строке записана строка $T$.

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

Выведите в стандартный поток вывода в $1$ строке целое число — максимально возможную длину поезда, который можно сформировать. Если невозможно сформировать ни $1$ поезда, выведите 0.

Критерии оценивания

• В тестах общей стоимостью $20\%$ баллов выполняется $M \le 10$, $N \le 10$.
• В тестах общей стоимостью $50\%$ баллов выполняется $M \le 50$, $N \le 50$.

Пример 1

5 5
OIOOI
OOIOI

7

Назовём депо, описываемое строкой $S$, депо S, а депо, описываемое строкой $T$, — депо T. Тогда, например, если сначала вывести на путь ожидания первый ($1$) вагон из депо S и первые $2$ вагона из депо T, а затем выводить вагоны в порядке: депо S, депо S, депо T, депо S, депо S, депо T, депо T, то можно сформировать поезд IOIOIOI длины $7$.

Кроме того, если сначала вывести на путь ожидания первый ($1$) вагон из депо S и первые $2$ вагона из депо T, а затем выводить вагоны в порядке: депо T, депо T, депо S, депо S, депо T, депо S, депо S, то также можно сформировать поезд длины $7$. Поскольку сформировать более длинный поезд невозможно, выводится $7$.

Пример 2

5 9
IIIII
IIIIIIIII

1

Обратите внимание, что поезд I, состоящий всего из $1$ вагона, также удовлетворяет условиям поезда.