Oppgavebeskrivelse

I kongeriket IOI har man nylig lagt en ny jernbane. Et tog som kjører på jernbanen i kongeriket IOI, består av flere vogner som er koblet sammen, og det finnes $2$ typer vogner: I og O. En vogn kan kun kobles sammen med en vogn av en annen type. Siden det dessuten må være førerhus i begge ender av toget, må vognene i begge ender av et tog være av typen I. Et tog representeres av en streng som dannes ved å sette sammen tegnene som angir vognenes typer i rekkefølge, og togets lengde er definert som lengden på denne strengen. Hvis man for eksempel kobler sammen vogner i rekkefølgen IOIOI, kan man danne et tog med lengde $5$, og én enkelt vogn I alene er et tog med lengde $1$. Man kan ikke danne et tog ved å sette vogner i en rekkefølge som OIOI eller IOOI.

Flere vogner er lagret i $2$ vognhaller. Inne i hver vognhall står vognene på én rekke. Når man setter sammen et tog, tar man vogner ut fra vognhallene og kobler dem sammen foran vognhallene. Den eneste vognen som kan tas ut fra en vognhall, er den som står nærmest utgangen av vognhallen, men rekkefølgen på hvilken av de to vognhallene man tar ut vogner fra, er valgfri.

Før man begynner å sette sammen et tog, kan man ta ut så mange vogner man vil fra vognhallene og flytte dem over på et eget ventespor. Vogner som er flyttet til ventesporet, kan ikke lenger brukes til å sette sammen toget senere. Dessuten, så snart man har begynt å sette sammen toget, kan man ikke flytte vogner fra vognhallene til ventesporet før sammensetningen er ferdig.

Når man setter sammen et tog, er det ikke nødvendig å bruke opp alle vognene i vognhallene. Det vil si at etter at toget er ferdig sammensatt, kan det gjerne stå igjen ubrukte vogner inne i vognhallene.

Siden det forventes at svært mange mennesker vil ta toget i kongeriket IOI, ønsker vi å sette sammen et så langt tog som mulig.

Figur: Midt under sammensetningen av et tog (øverst: ventespor; nederst til venstre: tog under sammensetning; til høyre: vognhall S og vognhall T); på dette tidspunktet kan ikke vogner i vognhallene flyttes til ventesporet. Denne figuren tilsvarer Eksempel 1.

Oppgave

Gitt informasjonen om vognene som er lagret i vognhallene, skriv et program som finner den maksimale mulige lengden på et tog som kan settes sammen. Rekken av vogner i hver vognhall representeres av en streng som kun består av de $2$ tegntypene I og O, og informasjonen om de $2$ vognhallene gis som henholdsvis en streng $S$ med lengde $M$ og en streng $T$ med lengde $N$. Hvert tegn representerer $1$ vogn, og tegnet er det samme som vogntypen. Det $1$. tegnet i strengen representerer vognen nærmest utgangen av vognhallen, og det siste tegnet representerer vognen lengst inne i vognhallen.

Begrensninger

• $1 \le M \le 2\,000$: lengden på strengen $S$.
• $1 \le N \le 2\,000$: lengden på strengen $T$.

Inndata

Les inn følgende data fra standard inndata.

• På den $1$. linjen står $M, N$ adskilt med mellomrom.
• På den $2$. linjen står strengen $S$.
• På den $3$. linjen står strengen $T$.

Utdata

Skriv ut til standard utdata på $1$ linje et heltall som representerer den maksimale lengden på et tog som kan settes sammen. Hvis ikke engang $1$ tog kan settes sammen, skriv ut 0.

Vurderingskriterier

• For $20\%$ av den totale poengsummen gjelder $M \le 10$, $N \le 10$.
• For $50\%$ av den totale poengsummen gjelder $M \le 50$, $N \le 50$.

Eksempel 1

5 5
OIOOI
OOIOI

7

La vognhallen representert ved $S$ kalles vognhall S, og la vognhallen representert ved $T$ kalles vognhall T. Hvis vi da for eksempel først tar ut den første ($1$) vognen fra vognhall S og de første $2$ vognene fra vognhall T til ventesporet, og deretter tar ut vogner i rekkefølgen vognhall S, vognhall S, vognhall T, vognhall S, vognhall S, vognhall T, vognhall T, kan vi sette sammen toget IOIOIOI med lengde $7$.

Alternativt kan vi, etter å ha tatt ut den første ($1$) vognen fra vognhall S og de første $2$ vognene fra vognhall T til ventesporet, også sette sammen et tog med lengde $7$ ved å ta ut vogner i rekkefølgen vognhall T, vognhall T, vognhall S, vognhall S, vognhall T, vognhall S, vognhall S. Siden det ikke er mulig å sette sammen et lengre tog enn dette, skriver vi ut $7$.

Eksempel 2

5 9
IIIII
IIIIIIIII

1

Merk at et tog I som kun består av $1$ vogn, også oppfyller kravene til et tog.