คำอธิบายโจทย์

ประเทศ 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$ ตู้ก็เป็นไปตามเงื่อนไขของขบวนรถไฟเช่นกัน