Умова задачі
У Королівстві IOI нещодавно проклали нову залізницю. Поїзд, що курсує залізницею Королівства IOI, складається з кількох зчеплених між собою вагонів, причому вагони бувають $2$ типів: I та O. Кожен вагон можна зчіплювати лише з вагоном іншого типу. Крім того, оскільки на обох кінцях поїзда потрібно облаштувати кабіни машиніста, крайні вагони з обох кінців поїзда повинні бути типу I. Поїзд подається рядком, утвореним послідовним з'єднанням символів, що позначають типи його вагонів, а довжиною поїзда вважається довжина цього рядка. Наприклад, зчепивши вагони в порядку IOIOI, можна сформувати поїзд довжини $5$, а один вагон I сам по собі утворює поїзд довжини $1$. Якщо ж розташувати вагони в порядку на зразок OIOI чи IOOI, сформувати поїзд неможливо.
Кілька вагонів зберігаються у $2$ депо. Усередині кожного депо вагони вишикувані в один ряд. Під час формування поїзда вагони виводять із депо й послідовно зчіплюють перед депо. Вивести з депо можна лише той вагон, який розташований найближче до виходу з цього депо, проте порядок того, з якого саме депо виводити черговий вагон, можна обирати вільно.
Перед початком формування поїзда можна вивести скільки завгодно вагонів із депо й перевести їх на окрему колію очікування. Вагони, переведені на колію очікування, надалі вже не можна використовувати для формування поїзда. Крім того, щойно формування поїзда розпочалося, аж до його завершення переводити вагони з депо на колію очікування не можна.
Під час формування поїзда не обов'язково використовувати всі вагони, що є в депо. Іншими словами, після завершення формування поїзда в депо можуть залишитися невикористані вагони.
Оскільки очікується, що в Королівстві IOI залізницею користуватиметься дуже багато людей, ми хочемо сформувати якомога довший поїзд.
Рисунок: У процесі формування поїзда (згори: колія очікування; знизу ліворуч: поїзд, що формується; праворуч: депо S та депо T); у цей момент переводити вагони з депо на колію очікування не можна. Цей рисунок відповідає Прикладу 1.
Завдання
За заданою інформацією про вагони, що зберігаються в депо, напишіть програму, яка визначає максимально можливу довжину поїзда, який можна сформувати. Ряд вагонів у кожному депо задається рядком, що складається лише із символів $2$ типів — I та O, причому інформація про $2$ депо подається відповідно у вигляді рядка $S$ довжини $M$ та рядка $T$ довжини $N$. Кожен символ позначає $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. Тоді, наприклад, якщо спочатку вивести на колію очікування перший ($1$) вагон із депо S та перші $2$ вагони з депо T, а потім виводити вагони в порядку: депо S, депо S, депо T, депо S, депо S, депо T, депо T, то можна сформувати поїзд IOIOIOI довжини $7$.
Крім того, якщо спочатку вивести на колію очікування перший ($1$) вагон із депо S та перші $2$ вагони з депо T, а потім виводити вагони в порядку: депо T, депо T, депо S, депо S, депо T, депо S, депо S, то також можна сформувати поїзд довжини $7$. Оскільки сформувати довший поїзд неможливо, виводиться $7$.
Приклад 2
5 9 IIIII IIIIIIIII
1
Зверніть увагу, що поїзд I, який складається лише з $1$ вагона, також задовольняє умови поїзда.