תיאור הבעיה

בממלכת 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$ בלבד מקיימת את התנאים של רכבת.