題目描述

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 也滿足作為列車的條件。