Enunciado del problema

En el Reino de IOI se acaba de construir un nuevo ferrocarril. Un tren que circula por el ferrocarril del Reino de IOI está formado por varios vagones acoplados entre sí, y existen $2$ tipos de vagones: I y O. Cada vagón solo puede acoplarse con un vagón de distinto tipo. Además, debido a que se deben instalar cabinas de conducción en ambos extremos del tren, los vagones situados en ambos extremos del tren deben ser del tipo I. Un tren se representa mediante una cadena formada al concatenar en orden los caracteres que indican el tipo de sus vagones, y la longitud del tren se define como la longitud de dicha cadena. Por ejemplo, acoplar vagones en el orden IOIOI permite formar un tren de longitud $5$, y un único vagón I por sí solo es un tren de longitud $1$. No es posible formar un tren disponiendo los vagones en un orden como OIOI o IOOI.

Varios vagones están almacenados en $2$ cocheras. Dentro de cada cochera, los vagones están alineados en una sola fila. Al formar un tren, se sacan vagones de las cocheras y se van acoplando delante de ellas. El único vagón que se puede sacar de una cochera es el que está más cerca de la entrada de esa cochera, pero el orden en que se decide de cuál de las dos cocheras sacar vagones es libre.

Antes de empezar a formar un tren, se puede sacar cualquier cantidad de vagones de las cocheras y moverlos a una vía de espera independiente. Los vagones movidos a la vía de espera ya no podrán utilizarse posteriormente para formar el tren. Además, una vez que se ha empezado a formar el tren, no se pueden mover vagones de las cocheras a la vía de espera hasta que termine la formación.

Al formar un tren, no es necesario agotar todos los vagones de las cocheras. Es decir, tras finalizar la formación del tren, pueden quedar vagones sin usar dentro de las cocheras.

Dado que se espera que muchísima gente viaje en el ferrocarril en el Reino de IOI, queremos formar un tren lo más largo posible.

Figura: En medio de la formación de un tren (arriba: vía de espera; abajo a la izquierda: tren en formación; derecha: cochera S y cochera T); en este momento no se pueden mover vagones de las cocheras a la vía de espera. Esta figura corresponde al Ejemplo 1.

Tarea

Dada la información de los vagones almacenados en las cocheras, escribe un programa para hallar el valor máximo de la longitud de un tren que se puede formar. La fila de vagones almacenada en cada cochera se representa mediante una cadena compuesta únicamente por los $2$ tipos de caracteres I y O, y la información de las $2$ cocheras se proporciona como una cadena $S$ de longitud $M$ y una cadena $T$ de longitud $N$, respectivamente. Cada carácter representa $1$ vagón, y dicho carácter coincide con el tipo de vagón. El $1$-er carácter de la cadena representa el vagón más cercano a la entrada de la cochera, y el último carácter representa el vagón situado más al fondo de la cochera.

Restricciones

• $1 \le M \le 2\,000$: la longitud de la cadena $S$.
• $1 \le N \le 2\,000$: la longitud de la cadena $T$.

Entrada

Lee los siguientes datos de la entrada estándar.

• En la $1$-ra línea están escritos $M, N$ separados por un espacio.
• En la $2$-da línea está escrita la cadena $S$.
• En la $3$-ra línea está escrita la cadena $T$.

Salida

Imprime en la salida estándar un entero en $1$ línea que represente la longitud máxima de un tren que se puede formar. Si no se puede formar ni siquiera $1$ tren, imprime 0.

Criterios de calificación

• Para el $20\%$ de la puntuación total, se cumple $M \le 10$, $N \le 10$.
• Para el $50\%$ de la puntuación total, se cumple $M \le 50$, $N \le 50$.

Ejemplo 1

5 5
OIOOI
OOIOI

7

Llamemos cochera S a la cochera representada por $S$, y cochera T a la cochera representada por $T$. Entonces, por ejemplo, tras sacar el primer ($1$) vagón de la cochera S y los primeros $2$ vagones de la cochera T a la vía de espera, si sacamos vagones en el orden: cochera S, cochera S, cochera T, cochera S, cochera S, cochera T, cochera T, podemos formar el tren IOIOIOI de longitud $7$.

Además, tras sacar el primer ($1$) vagón de la cochera S y los primeros $2$ vagones de la cochera T a la vía de espera, también podemos formar un tren de longitud $7$ sacando vagones en el orden: cochera T, cochera T, cochera S, cochera S, cochera T, cochera S, cochera S. Como no es posible formar un tren más largo que este, se imprime $7$.

Ejemplo 2

5 9
IIIII
IIIIIIIII

1

Ten en cuenta que un tren I formado por solo $1$ vagón también cumple las condiciones para ser un tren.