Problembeskrivning

I kungariket IOI har man nyligen anlagt en ny järnväg. Ett tåg som kör på järnvägen i kungariket IOI består av flera sammankopplade vagnar, och det finns $2$ typer av vagnar: I och O. En vagn kan endast kopplas ihop med en vagn av en annan typ. Eftersom det dessutom måste finnas förarhytter i båda ändarna av tåget måste vagnarna i båda ändarna av ett tåg vara av typen I. Ett tåg representeras av en sträng som bildas genom att man i ordning sätter ihop tecknen som anger vagnarnas typer, och tågets längd definieras som längden på denna sträng. Om man till exempel kopplar ihop vagnar i ordningen IOIOI kan man bilda ett tåg med längden $5$, och en ensam vagn I utgör i sig ett tåg med längden $1$. Man kan inte bilda ett tåg genom att ordna vagnar i en följd som OIOI eller IOOI.

Flera vagnar förvaras i $2$ depåer. Inuti varje depå står vagnarna på rad efter varandra. När man bildar ett tåg tar man ut vagnar ur depåerna och kopplar ihop dem framför depåerna. Den enda vagn som kan tas ut ur en depå är den som står närmast depåns infart, men i vilken ordning man väljer att ta ut vagnar från den ena eller den andra depån är fritt.

Innan man börjar bilda ett tåg kan man ta ut hur många vagnar man vill ur depåerna och flytta dem till ett separat väntespår. Vagnar som har flyttats till väntespåret kan därefter inte längre användas för att bilda tåget. När man väl har börjat bilda tåget kan man inte heller flytta några vagnar från depåerna till väntespåret förrän tågbildningen är avslutad.

När man bildar ett tåg behöver man inte använda upp alla vagnar i depåerna. Det gör alltså ingenting om det finns oanvända vagnar kvar i depåerna när tåget är färdigbildat.

Eftersom det förväntas att väldigt många människor kommer att åka tåg i kungariket IOI vill vi bilda ett så långt tåg som möjligt.

Figur: Mitt under bildandet av ett tåg (överst: väntespår; nederst till vänster: tåg under bildande; till höger: depå S och depå T); vid detta tillfälle kan vagnar i depåerna inte flyttas till väntespåret. Denna figur motsvarar Exempel 1.

Uppgift

Givet informationen om vagnarna som förvaras i depåerna, skriv ett program som beräknar den största möjliga längden på ett tåg som kan bildas. Raden av vagnar i varje depå representeras av en sträng som endast består av de $2$ teckentyperna I och O, och informationen om de $2$ depåerna ges som en sträng $S$ med längden $M$ respektive en sträng $T$ med längden $N$. Varje tecken representerar $1$ vagn och är detsamma som vagnens typ. Det $1$:a tecknet i strängen representerar vagnen närmast depåns infart, och det sista tecknet representerar vagnen längst in i depån.

Begränsningar

• $1 \le M \le 2\,000$: längden på strängen $S$.
• $1 \le N \le 2\,000$: längden på strängen $T$.

Indata

Läs in följande data från standardindata.

• På den $1$:a raden står $M, N$ separerade med ett blanksteg.
• På den $2$:a raden står strängen $S$.
• På den $3$:e raden står strängen $T$.

Utdata

Skriv ut ett heltal på $1$ rad till standardutdata som anger den maximala längden på ett tåg som kan bildas. Om inte ens $1$ tåg kan bildas, skriv ut 0.

Poängsättning

• För $20\%$ av den totala poängen gäller $M \le 10$, $N \le 10$.
• För $50\%$ av den totala poängen gäller $M \le 50$, $N \le 50$.

Exempel 1

5 5
OIOOI
OOIOI

7

Låt depån som representeras av $S$ kallas depå S och depån som representeras av $T$ kallas depå T. Om vi då till exempel först tar ut den första ($1$) vagnen från depå S och de första $2$ vagnarna från depå T till väntespåret, och därefter tar ut vagnar i ordningen depå S, depå S, depå T, depå S, depå S, depå T, depå T, kan vi bilda tåget IOIOIOI med längden $7$.

Alternativt kan vi, efter att ha tagit ut den första ($1$) vagnen från depå S och de första $2$ vagnarna från depå T till väntespåret, också bilda ett tåg med längden $7$ genom att ta ut vagnar i ordningen depå T, depå T, depå S, depå S, depå T, depå S, depå S. Eftersom det inte går att bilda ett längre tåg än så skriver vi ut $7$.

Exempel 2

5 9
IIIII
IIIIIIIII

1

Observera att även ett tåg I som består av endast $1$ vagn uppfyller villkoren för ett tåg.