題目描述
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 亦滿足作為列車嘅條件。