Lýsing á verkefni
Í konungsríkinu IOI var nýlega lögð ný járnbraut. Lest sem ekur á járnbraut konungsríkisins IOI samanstendur af nokkrum tengdum vögnum, og til eru $2$ tegundir af vögnum: I og O. Hvern vagn má aðeins tengja við vagn af annarri tegund. Þar að auki, vegna þess að koma þarf fyrir stýrishúsum á báðum endum lestarinnar, verða vagnarnir á báðum endum lestarinnar að vera af tegund I. Lest er táknuð með streng sem myndast með því að skeyta saman í röð stöfunum sem tákna tegundir vagna hennar, og lengd lestarinnar er skilgreind sem lengd þess strengs. Til dæmis, ef vagnar eru tengdir í röðinni IOIOI má mynda lest af lengd $5$, og stakur vagn I einn og sér er lest af lengd $1$. Ekki er hægt að mynda lest með því að raða vögnum í röð eins og OIOI eða IOOI.
Nokkrir vagnar eru geymdir í $2$ vagnaskemmum. Inni í hvorri vagnaskemmu standa vagnarnir í einni röð. Þegar lest er mynduð eru vagnar teknir út úr vagnaskemmunum og tengdir saman fyrir framan þær. Eini vagninn sem hægt er að taka út úr vagnaskemmu er sá sem er næstur inngangi þeirrar vagnaskemmu, en röðin á því úr hvorri vagnaskemmunni vagnar eru teknir er frjáls.
Áður en byrjað er að mynda lest má taka eins marga vagna og óskað er út úr vagnaskemmunum og færa þá yfir á sérstakt biðspor. Vagna sem færðir hafa verið á biðsporið er ekki hægt að nota síðar til að mynda lestina. Einnig, um leið og byrjað er að mynda lestina er ekki hægt að færa vagna úr vagnaskemmunum yfir á biðsporið þar til myndun lestarinnar er lokið.
Þegar lest er mynduð er ekki nauðsynlegt að nota alla vagnana í vagnaskemmunum. Það er að segja, eftir að myndun lestarinnar lýkur mega ónotaðir vagnar verða eftir inni í vagnaskemmunum.
Þar sem búist er við að mjög margir muni ferðast með járnbrautinni í konungsríkinu IOI viljum við mynda eins langa lest og mögulegt er.
Mynd: Í miðju ferli við að mynda lest (efst: biðspor; neðst til vinstri: lest í myndun; til hægri: vagnaskemma S og vagnaskemma T); á þessum tímapunkti er ekki hægt að færa vagna úr vagnaskemmunum yfir á biðsporið. Þessi mynd samsvarar Dæmi 1.
Verkefni
Gefnar upplýsingar um vagnana sem geymdir eru í vagnaskemmunum, skrifið forrit til að finna mestu mögulegu lengd lestar sem hægt er að mynda. Röð vagna í hvorri vagnaskemmu er táknuð með streng sem samanstendur eingöngu af $2$ stafategundunum I og O, og upplýsingar um $2$ vagnaskemmurnar eru gefnar sem strengur $S$ af lengd $M$ annars vegar og strengur $T$ af lengd $N$ hins vegar. Hver stafur táknar $1$ vagn og er sá sami og tegund vagnsins. $1$. stafur strengsins táknar vagninn sem er næstur inngangi vagnaskemmunnar, og síðasti stafurinn táknar vagninn sem er innst í vagnaskemmunni.
Takmarkanir
- $1 \le M \le 2\,000$: lengd strengsins $S$.
- $1 \le N \le 2\,000$: lengd strengsins $T$.
Inntak
Lesið eftirfarandi gögn úr staðalinntaki.
- Á $1$. línu eru $M, N$ skrifuð aðskilin með bili.
- Á $2$. línu er strengurinn $S$ skrifaður.
- Á $3$. línu er strengurinn $T$ skrifaður.
Úttak
Skrifið út í staðalúttak í $1$ línu heiltölu sem táknar hámarkslengd lestar sem hægt er að mynda. Ef ekki er hægt að mynda jafnvel $1$ lest, skrifið 0.
Stigagjöf
- Fyrir $20\%$ af heildarstigum gildir $M \le 10$, $N \le 10$.
- Fyrir $50\%$ af heildarstigum gildir $M \le 50$, $N \le 50$.
Dæmi 1
5 5 OIOOI OOIOI
7
Köllum vagnaskemmuna sem táknuð er með $S$ vagnaskemmu S, og vagnaskemmuna sem táknuð er með $T$ vagnaskemmu T. Ef við tökum til dæmis fyrst út fyrsta ($1$) vagninn úr vagnaskemmu S og fyrstu $2$ vagnana úr vagnaskemmu T á biðsporið, og tökum síðan út vagna í röðinni: vagnaskemma S, vagnaskemma S, vagnaskemma T, vagnaskemma S, vagnaskemma S, vagnaskemma T, vagnaskemma T, getum við myndað lestina IOIOIOI af lengd $7$.
Auk þess, eftir að hafa tekið út fyrsta ($1$) vagninn úr vagnaskemmu S og fyrstu $2$ vagnana úr vagnaskemmu T á biðsporið, má einnig mynda lest af lengd $7$ með því að taka út vagna í röðinni: vagnaskemma T, vagnaskemma T, vagnaskemma S, vagnaskemma S, vagnaskemma T, vagnaskemma S, vagnaskemma S. Þar sem ómögulegt er að mynda lengri lest en þetta er skrifað út $7$.
Dæmi 2
5 9 IIIII IIIIIIIII
1
Athugið að lestin I sem samanstendur af aðeins $1$ vagni uppfyllir einnig skilyrði lestar.