Есептің шарты

IOI елінде жақында жаңа теміржол салынды. IOI елінің теміржолымен жүретін пойыз бір-біріне тіркелген бірнеше вагоннан тұрады, ал вагондардың I және O деген $2$ түрі бар. Әрбір вагонды тек басқа түрдегі вагонмен ғана тіркеуге болады. Сонымен қатар, пойыздың екі шетінде машинист кабинасы орналасуы тиіс болғандықтан, пойыздың екі шетіндегі вагондар міндетті түрде I түрінде болуы керек. Пойыз оның вагондарының түрлерін білдіретін таңбаларды ретімен жалғау арқылы алынған жолмен өрнектеледі, ал пойыздың ұзындығы сол жолдың ұзындығына тең деп есептеледі. Мысалы, вагондарды IOIOI ретімен тіркесек, ұзындығы $5$ болатын пойыз құрастыруға болады, ал жалғыз I вагонының өзі ұзындығы $1$ болатын пойыз болып табылады. Вагондарды OIOI немесе IOOI сияқты ретпен қойып пойыз құрастыру мүмкін емес.

Бірнеше вагон $2$ депода сақтаулы тұр. Әрбір депоның ішінде вагондар бір қатарға тізіліп тұр. Пойыз құрастырған кезде вагондарды деподан шығарып, депоның алдында бір-біріне тіркейді. Деподан тек сол депоның шығаберісіне ең жақын тұрған вагонды ғана шығаруға болады, бірақ вагонды қай деподан шығару ретін еркін таңдауға болады.

Пойызды құрастыруды бастамас бұрын, деподан қалағаныңызша вагон шығарып, оларды бөлек күту рельсіне ауыстыруға болады. Күту рельсіне ауыстырылған вагондарды бұдан былай пойыз құрастыру үшін пайдалануға болмайды. Сондай-ақ, пойызды құрастыру басталғаннан кейін, ол аяқталғанға дейін деподан күту рельсіне вагон ауыстыруға болмайды.

Пойыз құрастырған кезде деподағы барлық вагондарды түгел пайдалану міндетті емес. Яғни, пойызды құрастырып болғаннан кейін депо ішінде пайдаланылмаған вагондар қалып қойса да болады.

IOI елінде теміржолмен жүретін адамдар өте көп болады деп күтілгендіктен, біз мүмкіндігінше ұзын пойыз құрастырғымыз келеді.

Сурет: Пойызды құрастыру барысы (жоғарыда: күту рельсі; төменгі сол жақта: құрастырылып жатқан пойыз; оң жақта: S депосы мен T депосы); бұл сәтте деподағы вагондарды күту рельсіне ауыстыруға болмайды. Бұл сурет 1-мысалға сәйкес келеді.

Тапсырма

Депода сақталған вагондар туралы ақпарат берілгенде, құрастыруға болатын пойыз ұзындығының ең үлкен мәнін табатын программа жазыңыз. Әрбір депода сақталған вагондар тізбегі тек I және O деген $2$ түрлі таңбадан тұратын жолмен өрнектеледі, ал $2$ депо туралы ақпарат сәйкесінше ұзындығы $M$ болатын $S$ жолы және ұзындығы $N$ болатын $T$ жолы ретінде беріледі. Әрбір таңба $1$ вагонды білдіреді және ол таңба вагонның түрімен бірдей. Жолдың $1$-ші таңбасы депоның шығаберісіне ең жақын вагонды, ал соңғы таңбасы депоның ең түбіндегі вагонды білдіреді.

Шектеулер

• $1 \le M \le 2\,000$: $S$ жолының ұзындығы.
• $1 \le N \le 2\,000$: $T$ жолының ұзындығы.

Кіріс деректер

Стандартты кірістен келесі деректерді оқыңыз.

• $1$-ші жолда бос орын арқылы бөлінген $M, N$ жазылған.
• $2$-ші жолда $S$ жолы жазылған.
• $3$-ші жолда $T$ жолы жазылған.

Шығыс деректер

Стандартты шығысқа $1$ жолда құрастыруға болатын пойыз ұзындығының ең үлкен мәнін білдіретін бүтін санды шығарыңыз. Егер тіпті $1$ пойыз да құрастыру мүмкін болмаса, 0 шығарыңыз.

Бағалау критерийлері

• Жалпы ұпайдың $20\%$ құрайтын тест деректерінде $M \le 10$, $N \le 10$ шарттары орындалады.
• Жалпы ұпайдың $50\%$ құрайтын тест деректерінде $M \le 50$, $N \le 50$ шарттары орындалады.

1-мысал

5 5
OIOOI
OOIOI

7

$S$ арқылы өрнектелген депоны S депосы деп, ал $T$ арқылы өрнектелген депоны T депосы деп атайық. Сонда, мысалы, S депосынан алғашқы $1$ вагонды, T депосынан алғашқы $2$ вагонды күту рельсіне шығарып қойғаннан кейін, вагондарды S депосы, S депосы, T депосы, S депосы, S депосы, T депосы, T депосы ретімен шығарсақ, ұзындығы $7$ болатын IOIOIOI пойызын құрастыруға болады.

Бұдан бөлек, S депосынан алғашқы $1$ вагонды, T депосынан алғашқы $2$ вагонды күту рельсіне шығарып қойғаннан кейін, вагондарды T депосы, T депосы, S депосы, S депосы, T депосы, S депосы, S депосы ретімен шығару арқылы да ұзындығы $7$ болатын пойыз құрастыруға болады. Бұдан ұзын пойыз құрастыру мүмкін болмағандықтан, $7$ шығарылады.

2-мысал

5 9
IIIII
IIIIIIIII

1

Тек $1$ вагоннан ғана тұратын I пойызы да пойыз шартын қанағаттандыратынына назар аударыңыз.