Tehtävänanto

IOI-valtakuntaan on hiljattain rakennettu uusi rautatie. IOI-valtakunnan rautatiellä kulkeva juna koostuu useista toisiinsa kytketyistä vaunuista, ja vaunuja on $2$ tyyppiä: I ja O. Vaunun voi kytkeä ainoastaan erityyppiseen vaunuun. Lisäksi, koska junan molempiin päihin on sijoitettava ohjaamo, junan molemmissa päissä olevien vaunujen on oltava tyyppiä I. Junaa esittää merkkijono, joka muodostuu ketjuttamalla sen vaunujen tyyppejä kuvaavat merkit järjestyksessä, ja junan pituus määritellään tämän merkkijonon pituudeksi. Esimerkiksi kytkemällä vaunut järjestyksessä IOIOI voidaan muodostaa pituudeltaan $5$ oleva juna, ja yksittäinen vaunu I yksinään on pituudeltaan $1$ oleva juna. Junaa ei voida muodostaa asettamalla vaunuja esimerkiksi järjestykseen OIOI tai IOOI.

Useita vaunuja säilytetään $2$ varikossa. Kummankin varikon sisällä vaunut ovat yhdessä jonossa. Kun junaa muodostetaan, vaunuja otetaan ulos varikoista ja kytketään toisiinsa varikoiden edessä. Varikosta voidaan ottaa ulos vain se vaunu, joka on lähimpänä kyseisen varikon suuaukkoa, mutta järjestys, jolla vaunuja otetaan ulos kummastakin varikosta, on vapaasti valittavissa.

Ennen kuin junan muodostaminen aloitetaan, varikoista voidaan ottaa ulos haluttu määrä vaunuja ja siirtää ne erilliselle odotusraiteelle. Odotusraiteelle siirrettyjä vaunuja ei voida enää myöhemmin käyttää junan muodostamiseen. Lisäksi heti kun junan muodostaminen on aloitettu, vaunuja ei voida siirtää varikoista odotusraiteelle ennen kuin junan muodostaminen on päättynyt.

Junaa muodostettaessa ei ole välttämätöntä käyttää kaikkia varikoissa olevia vaunuja. Toisin sanoen junan muodostamisen päätyttyä varikoihin saa jäädä käyttämättömiä vaunuja.

Koska IOI-valtakunnassa odotetaan olevan erittäin paljon junamatkustajia, haluamme muodostaa mahdollisimman pitkän junan.

Kuva: Junan muodostaminen on kesken (ylhäällä: odotusraide; alhaalla vasemmalla: muodostettava juna; oikealla: varikko S ja varikko T); tässä vaiheessa varikoissa olevia vaunuja ei voi siirtää odotusraiteelle. Tämä kuva vastaa Esimerkkiä 1.

Tehtävä

Kun varikoissa säilytettävien vaunujen tiedot annetaan, kirjoita ohjelma, joka etsii suurimman mahdollisen pituuden muodostettavissa olevalle junalle. Kummassakin varikossa olevien vaunujen jono esitetään merkkijonona, joka koostuu vain $2$ merkkityypistä I ja O, ja $2$ varikon tiedot annetaan pituudeltaan $M$ olevana merkkijonona $S$ ja pituudeltaan $N$ olevana merkkijonona $T$. Jokainen merkki kuvaa $1$ vaunua, ja merkki on sama kuin vaunun tyyppi. Merkkijonon $1$. merkki kuvaa lähimpänä varikon suuaukkoa olevaa vaunua, ja viimeinen merkki kuvaa varikon perimmäisenä olevaa vaunua.

Rajoitukset

• $1 \le M \le 2\,000$: merkkijonon $S$ pituus.
• $1 \le N \le 2\,000$: merkkijonon $T$ pituus.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• $1$. rivillä ovat luvut $M, N$ välilyönnillä erotettuina.
• $2$. rivillä on merkkijono $S$.
• $3$. rivillä on merkkijono $T$.

Tuloste

Tulosta vakiotulosteeseen $1$ riville kokonaisluku, joka ilmaisee muodostettavissa olevan junan suurimman mahdollisen pituuden. Jos yhtäkään ($1$) junaa ei voida muodostaa, tulosta 0.

Arvosteluperusteet

• $20\%$:ssa pisteistä pätee $M \le 10$, $N \le 10$.
• $50\%$:ssa pisteistä pätee $M \le 50$, $N \le 50$.

Esimerkki 1

5 5
OIOOI
OOIOI

7

Olkoon merkkijonon $S$ kuvaama varikko nimeltään varikko S ja merkkijonon $T$ kuvaama varikko nimeltään varikko T. Tällöin esimerkiksi, kun varikosta S otetaan ensin $1$ ensimmäinen vaunu ja varikosta T $2$ ensimmäistä vaunua odotusraiteelle, ja sen jälkeen vaunuja otetaan ulos järjestyksessä varikko S, varikko S, varikko T, varikko S, varikko S, varikko T, varikko T, voidaan muodostaa pituudeltaan $7$ oleva juna IOIOIOI.

Lisäksi, kun varikosta S on otettu $1$ ensimmäinen vaunu ja varikosta T $2$ ensimmäistä vaunua odotusraiteelle, pituudeltaan $7$ oleva juna voidaan muodostaa myös ottamalla vaunuja ulos järjestyksessä varikko T, varikko T, varikko S, varikko S, varikko T, varikko S, varikko S. Koska tätä pidempää junaa ei voida muodostaa, tulostetaan $7$.

Esimerkki 2

5 9
IIIII
IIIIIIIII

1

Huomaa, että vain $1$ vaunusta koostuva juna I täyttää myös junan ehdot.