بيان المسألة

في مملكة 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 إلى سكة الانتظار، يمكن أيضًا تكوين قطار طوله $7$ بإخراج العربات بالترتيب: المستودع T، المستودع T، المستودع S، المستودع S، المستودع T، المستودع S، المستودع S. وبما أنه لا يمكن تكوين قطار أطول من ذلك، نطبع $7$.

مثال 2

5 9
IIIII
IIIIIIIII

1

لاحظ أن القطار I المكون من عربة $1$ فقط يحقق أيضًا شروط القطار.