Treść zadania

W Królestwie IOI wybudowano niedawno nową linię kolejową. Pociąg kursujący po kolei Królestwa IOI składa się z kilku połączonych ze sobą wagonów, przy czym istnieją $2$ rodzaje wagonów: I oraz O. Każdy wagon może być połączony wyłącznie z wagonem innego rodzaju. Ponadto, ze względu na konieczność umieszczenia kabin maszynisty na obu końcach pociągu, wagony na obu końcach pociągu muszą być rodzaju I. Pociąg jest reprezentowany przez napis powstały przez połączenie po kolei znaków oznaczających rodzaje kolejnych wagonów, a długość pociągu definiujemy jako długość tego napisu. Na przykład połączenie wagonów w kolejności IOIOI pozwala utworzyć pociąg o długości $5$, a pojedynczy wagon I sam w sobie stanowi pociąg o długości $1$. Nie można utworzyć pociągu, ustawiając wagony w kolejności takiej jak OIOI czy IOOI.

Pewna liczba wagonów znajduje się w $2$ zajezdniach. Wewnątrz każdej zajezdni wagony stoją w jednym rzędzie. Podczas formowania pociągu wagony są wyprowadzane z zajezdni i łączone przed zajezdniami. Z zajezdni można wyprowadzić wyłącznie wagon znajdujący się najbliżej wyjazdu z tej zajezdni, natomiast kolejność wyboru, z której z dwóch zajezdni wyprowadzamy kolejny wagon, jest dowolna.

Przed rozpoczęciem formowania pociągu można wyprowadzić dowolną liczbę wagonów z zajezdni i przestawić je na osobny tor postojowy. Wagonów przestawionych na tor postojowy nie można już później użyć do formowania pociągu. Co więcej, gdy formowanie pociągu zostanie już rozpoczęte, aż do jego zakończenia nie można przestawiać wagonów z zajezdni na tor postojowy.

Podczas formowania pociągu nie trzeba wykorzystać wszystkich wagonów znajdujących się w zajezdniach. Oznacza to, że po zakończeniu formowania pociągu w zajezdniach mogą pozostać niewykorzystane wagony.

Ponieważ oczekuje się, że w Królestwie IOI koleją będzie podróżować bardzo wiele osób, chcemy uformować jak najdłuższy pociąg.

Rysunek: W trakcie formowania pociągu (u góry: tor postojowy; na dole po lewej: formowany pociąg; po prawej: zajezdnia S oraz zajezdnia T); w tym momencie nie można już przestawiać wagonów z zajezdni na tor postojowy. Rysunek ten odpowiada Przykładowi 1.

Zadanie

Mając dane informacje o wagonach zgromadzonych w zajezdniach, napisz program, który wyznaczy maksymalną możliwą długość pociągu, jaki można uformować. Rząd wagonów w każdej zajezdni jest reprezentowany przez napis składający się wyłącznie z $2$ rodzajów znaków I oraz O, a informacje o $2$ zajezdniach są podane odpowiednio jako napis $S$ o długości $M$ oraz napis $T$ o długości $N$. Każdy znak reprezentuje $1$ wagon i odpowiada rodzajowi tego wagonu. $1$-szy znak napisu oznacza wagon znajdujący się najbliżej wyjazdu z zajezdni, a ostatni znak oznacza wagon znajdujący się najgłębiej w zajezdni.

Ograniczenia

• $1 \le M \le 2\,000$: długość napisu $S$.
• $1 \le N \le 2\,000$: długość napisu $T$.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• W $1$-szym wierszu zapisane są liczby $M, N$ oddzielone spacją.
• W $2$-gim wierszu zapisany jest napis $S$.
• W $3$-cim wierszu zapisany jest napis $T$.

Wyjście

Wypisz na standardowe wyjście w $1$ wierszu liczbę całkowitą oznaczającą maksymalną możliwą długość pociągu, jaki można uformować. Jeśli nie da się uformować ani $1$ pociągu, wypisz 0.

Kryteria oceniania

• Dla danych testowych wartych $20\%$ punktów zachodzi $M \le 10$, $N \le 10$.
• Dla danych testowych wartych $50\%$ punktów zachodzi $M \le 50$, $N \le 50$.

Przykład 1

5 5
OIOOI
OOIOI

7

Nazwijmy zajezdnię opisaną napisem $S$ zajezdnią S, a zajezdnię opisaną napisem $T$ — zajezdnią T. Wówczas, na przykład, po wyprowadzeniu pierwszego ($1$) wagonu z zajezdni S oraz pierwszych $2$ wagonów z zajezdni T na tor postojowy, jeśli będziemy wyprowadzać wagony w kolejności: zajezdnia S, zajezdnia S, zajezdnia T, zajezdnia S, zajezdnia S, zajezdnia T, zajezdnia T, to uformujemy pociąg IOIOIOI o długości $7$.

Ponadto, po wyprowadzeniu pierwszego ($1$) wagonu z zajezdni S oraz pierwszych $2$ wagonów z zajezdni T na tor postojowy, pociąg o długości $7$ można również uformować, wyprowadzając wagony w kolejności: zajezdnia T, zajezdnia T, zajezdnia S, zajezdnia S, zajezdnia T, zajezdnia S, zajezdnia S. Ponieważ nie da się uformować dłuższego pociągu, wypisujemy $7$.

Przykład 2

5 9
IIIII
IIIIIIIII

1

Zwróć uwagę, że pociąg I składający się tylko z $1$ wagonu również spełnia warunki pociągu.