Aufgabenstellung

Im Königreich IOI wurde kürzlich eine neue Eisenbahnstrecke gebaut. Ein Zug, der auf der Eisenbahn des Königreichs IOI fährt, besteht aus mehreren miteinander gekoppelten Wagen, wobei es $2$ Arten von Wagen gibt: I und O. Ein Wagen kann nur mit einem Wagen einer anderen Art gekoppelt werden. Da außerdem an beiden Enden eines Zuges Führerstände eingerichtet werden müssen, müssen die Wagen an beiden Enden eines Zuges vom Typ I sein. Ein Zug wird durch eine Zeichenkette dargestellt, die entsteht, wenn man die Zeichen für die Wagenarten der Reihe nach aneinanderhängt, und die Länge des Zuges ist als die Länge dieser Zeichenkette definiert. Wenn man beispielsweise Wagen in der Reihenfolge IOIOI koppelt, kann man einen Zug der Länge $5$ zusammenstellen, und ein einzelner Wagen I allein ist ein Zug der Länge $1$. Wenn man Wagen in einer Reihenfolge wie OIOI oder IOOI anordnet, kann man keinen Zug zusammenstellen.

Mehrere Wagen sind in $2$ Depots untergebracht. In jedem Depot stehen die Wagen in einer einzigen Reihe hintereinander. Beim Zusammenstellen eines Zuges werden Wagen aus den Depots geholt und vor den Depots miteinander gekoppelt. Aus einem Depot kann jeweils nur der Wagen herausgeholt werden, der dem Eingang des Depots am nächsten steht, aber die Reihenfolge, aus welchem der beiden Depots man jeweils einen Wagen holt, ist frei wählbar.

Bevor man mit dem Zusammenstellen eines Zuges beginnt, kann man beliebig viele Wagen aus den Depots holen und auf ein separates Wartegleis verschieben. Wagen, die einmal auf das Wartegleis verschoben wurden, können danach nicht mehr zum Zusammenstellen des Zuges verwendet werden. Sobald man einmal mit dem Zusammenstellen des Zuges begonnen hat, können bis zum Ende der Zusammenstellung keine Wagen mehr aus den Depots auf das Wartegleis verschoben werden.

Beim Zusammenstellen eines Zuges müssen nicht alle Wagen in den Depots aufgebraucht werden. Das heißt, nach dem Zusammenstellen des Zuges dürfen nicht verwendete Wagen in den Depots zurückbleiben.

Da erwartet wird, dass im Königreich IOI sehr viele Menschen mit der Eisenbahn fahren werden, möchten wir einen möglichst langen Zug zusammenstellen.

Abbildung: Mitten beim Zusammenstellen eines Zuges (oben: Wartegleis; unten links: Zug in Zusammenstellung; rechts: Depot S und Depot T); zu diesem Zeitpunkt können keine Wagen aus den Depots auf das Wartegleis verschoben werden. Diese Abbildung entspricht Beispiel 1.

Aufgabe

Gegeben die Informationen über die in den Depots untergebrachten Wagen, schreiben Sie ein Programm, das die maximale Länge eines Zuges berechnet, der zusammengestellt werden kann. Die Reihe der in jedem Depot untergebrachten Wagen wird durch eine Zeichenkette dargestellt, die nur aus den $2$ Zeichenarten I und O besteht, und die Informationen über die $2$ Depots werden als Zeichenkette $S$ der Länge $M$ bzw. als Zeichenkette $T$ der Länge $N$ angegeben. Jedes Zeichen steht für $1$ Wagen und stimmt mit dem Typ des Wagens überein. Das $1$. Zeichen der Zeichenkette steht für den Wagen, der dem Eingang des Depots am nächsten ist, und das letzte Zeichen steht für den Wagen, der sich ganz hinten im Depot befindet.

Einschränkungen

• $1 \le M \le 2\,000$: die Länge der Zeichenkette $S$.
• $1 \le N \le 2\,000$: die Länge der Zeichenkette $T$.

Eingabe

Lesen Sie die folgenden Daten von der Standardeingabe.

• In der $1$. Zeile stehen $M, N$, getrennt durch ein Leerzeichen.
• In der $2$. Zeile steht die Zeichenkette $S$.
• In der $3$. Zeile steht die Zeichenkette $T$.

Ausgabe

Geben Sie auf der Standardausgabe in $1$ Zeile eine ganze Zahl aus, die die maximale Länge eines zusammenstellbaren Zuges angibt. Falls kein einziger ($1$) Zug zusammengestellt werden kann, geben Sie 0 aus.

Bewertung

• Für $20\%$ der Gesamtpunktzahl gilt $M \le 10$, $N \le 10$.
• Für $50\%$ der Gesamtpunktzahl gilt $M \le 50$, $N \le 50$.

Beispiel 1

5 5
OIOOI
OOIOI

7

Sei das durch $S$ dargestellte Depot das Depot S und das durch $T$ dargestellte Depot das Depot T. Wenn man nun beispielsweise den ersten ($1$) Wagen aus Depot S und die ersten $2$ Wagen aus Depot T auf das Wartegleis stellt und danach Wagen in der Reihenfolge Depot S, Depot S, Depot T, Depot S, Depot S, Depot T, Depot T herausholt, kann man den Zug IOIOIOI der Länge $7$ zusammenstellen.

Außerdem kann man, nachdem man den ersten ($1$) Wagen aus Depot S und die ersten $2$ Wagen aus Depot T auf das Wartegleis gestellt hat, auch dadurch einen Zug der Länge $7$ zusammenstellen, dass man Wagen in der Reihenfolge Depot T, Depot T, Depot S, Depot S, Depot T, Depot S, Depot S herausholt. Da kein längerer Zug zusammengestellt werden kann, wird $7$ ausgegeben.

Beispiel 2

5 9
IIIII
IIIIIIIII

1

Beachten Sie, dass auch ein nur aus $1$ Wagen bestehender Zug I die Bedingungen für einen Zug erfüllt.