Énoncé du problème

Au royaume de l'IOI, une nouvelle voie ferrée vient d'être construite. Un train circulant sur la voie ferrée du royaume de l'IOI est constitué de plusieurs wagons attelés ensemble, et il existe $2$ types de wagons : I et O. Un wagon ne peut être attelé qu'à un wagon d'un type différent. De plus, comme il faut installer une cabine de conduite aux deux extrémités du train, les wagons situés aux deux extrémités d'un train doivent impérativement être de type I. Un train est représenté par une chaîne de caractères formée en concaténant dans l'ordre les caractères représentant le type de ses wagons, et la longueur du train correspond à la longueur de cette chaîne. Par exemple, atteler des wagons dans l'ordre IOIOI permet de former un train de longueur $5$, et un wagon I seul constitue un train de longueur $1$. Il est impossible de former un train en disposant des wagons dans un ordre tel que OIOI ou IOOI.

Plusieurs wagons sont entreposés dans $2$ dépôts. Dans chaque dépôt, les wagons sont alignés sur une seule file. Pour former un train, on sort des wagons des dépôts et on les attelle les uns aux autres devant les dépôts. Le seul wagon que l'on peut sortir d'un dépôt est celui qui est le plus proche de l'entrée de ce dépôt, mais l'ordre dans lequel on choisit de sortir les wagons de l'un ou l'autre des deux dépôts est libre.

Avant de commencer à former un train, on peut sortir autant de wagons que l'on veut des dépôts et les placer sur une voie d'attente séparée. Les wagons déplacés sur la voie d'attente ne pourront plus être utilisés par la suite pour former le train. De plus, une fois que la formation du train a commencé, il n'est plus possible de déplacer des wagons des dépôts vers la voie d'attente jusqu'à ce que la formation soit terminée.

Lorsqu'on forme un train, il n'est pas nécessaire d'utiliser tous les wagons présents dans les dépôts. Autrement dit, une fois la formation du train achevée, il peut rester des wagons inutilisés dans les dépôts.

Comme on prévoit que de très nombreuses personnes emprunteront le train au royaume de l'IOI, on souhaite former un train aussi long que possible.

Figure : En cours de formation d'un train (en haut : voie d'attente ; en bas à gauche : train en cours de formation ; à droite : dépôt S et dépôt T) ; à ce stade, on ne peut plus déplacer de wagons des dépôts vers la voie d'attente. Cette figure correspond à l'Exemple 1.

Tâche

Étant donné les informations sur les wagons entreposés dans les dépôts, écrivez un programme déterminant la longueur maximale d'un train qu'il est possible de former. La file de wagons entreposée dans chaque dépôt est représentée par une chaîne composée uniquement des $2$ types de caractères I et O, et les informations des $2$ dépôts sont données respectivement sous la forme d'une chaîne $S$ de longueur $M$ et d'une chaîne $T$ de longueur $N$. Chaque caractère représente $1$ wagon et correspond au type de ce wagon. Le $1$-er caractère de la chaîne représente le wagon le plus proche de l'entrée du dépôt, et le dernier caractère représente le wagon situé tout au fond du dépôt.

Contraintes

• $1 \le M \le 2\,000$ : la longueur de la chaîne $S$.
• $1 \le N \le 2\,000$ : la longueur de la chaîne $T$.

Entrée

Lisez les données suivantes depuis l'entrée standard.

• Sur la $1$-re ligne sont écrits $M, N$ séparés par un espace.
• Sur la $2$-e ligne est écrite la chaîne $S$.
• Sur la $3$-e ligne est écrite la chaîne $T$.

Sortie

Affichez sur la sortie standard, sur $1$ seule ligne, l'entier représentant la longueur maximale d'un train pouvant être formé. Si l'on ne peut même pas former $1$ train, affichez 0.

Barème

• Pour $20\%$ des points, $M \le 10$ et $N \le 10$.
• Pour $50\%$ des points, $M \le 50$ et $N \le 50$.

Exemple 1

5 5
OIOOI
OOIOI

7

Appelons dépôt S le dépôt représenté par $S$, et dépôt T le dépôt représenté par $T$. Alors, par exemple, après avoir sorti le $1$-er wagon du dépôt S et les $2$ premiers wagons du dépôt T pour les mettre en attente, si l'on sort ensuite les wagons dans l'ordre : dépôt S, dépôt S, dépôt T, dépôt S, dépôt S, dépôt T, dépôt T, on peut former le train IOIOIOI de longueur $7$.

Par ailleurs, après avoir sorti le $1$-er wagon du dépôt S et les $2$ premiers wagons du dépôt T pour les mettre en attente, on peut aussi former un train de longueur $7$ en sortant les wagons dans l'ordre : dépôt T, dépôt T, dépôt S, dépôt S, dépôt T, dépôt S, dépôt S. Comme il est impossible de former un train plus long, on affiche $7$.

Exemple 2

5 9
IIIII
IIIIIIIII

1

Notez qu'un train I composé d'un seul ($1$) wagon remplit lui aussi les conditions d'un train.