说明

IOI 国最近铺设了新的铁路。在 IOI 国铁路上运行的列车由若干节车厢连接而成，车厢有 I 和 O 两种类型。车厢只能与不同类型的车厢相连。此外，由于需要设置驾驶室，列车两端的车厢类型必须是 I。列车可以用表示车厢类型的字符按顺序连接而成的字符串来表示，列车的长度即为该字符串的长度。例如，按 IOIOI 的顺序连接车厢可以编成长度为 5 的列车，而单节车厢 I 本身就是长度为 1 的列车。按照 OIOI 或 IOOI 的顺序排列车厢则无法编成列车。

一些车厢被存放在两个车库中。每个车库内的车厢排成一列。编组列车时，需要从车库中取出车厢并在车库前进行连接。每次只能取出最靠近车库入口的车厢，但可以从任意一个车库取车的顺序是自由的。

在开始编组列车之前，可以任意多次地将车厢从车库取出并移到另一条备用轨道上。一旦移到备用轨道，该车厢今后就不能再用于编组列车。此外，一旦开始编组一列列车，在该次编组完成之前，不能将车厢从车库移到备用轨道。

编组列车时，不必用完车库内的所有车厢。也就是说，列车编组完成后，车库内可能还留有未使用的车厢。

IOI 国预计会有非常多的乘客乘坐铁路，因此希望编组出尽可能长的列车。

:::align{center}

图：正在编组列车的过程中，此时不能将车库内的车厢移到备用轨道。此图对应于样例 1。 :::

任务

给定存放在车库中的车厢信息，编写一个程序，求出能够编组的列车长度的最大值。每个车库中存放的车厢序列用一个仅由字符 I 和 O 组成的字符串表示，两个车库的信息分别作为长度为 $M$ 的字符串 $S$ 和长度为 $N$ 的字符串 $T$ 给出。每个字符代表一节车厢，其字符与车厢类型相同。字符串的第一个字符代表最靠近车库入口的车厢，末尾字符代表车库最里面的车厢。

输入格式

从标准输入读取以下数据。

• 第一行包含两个用空格分隔的整数 $M$ 和 $N$。
• 第二行包含字符串 $S$。
• 第三行包含字符串 $T$。

输出格式

向标准输出输出一行，包含一个整数，表示能够编组的列车长度的最大值。如果无法编组出任何列车，则输出 $0$。

5 5
OIOOI
OOIOI

7

5 9
IIIII
IIIIIIIII

1

提示

样例解释 1

将由 $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

请注意，仅由一节车厢 I 组成的列车也满足列车的条件。

限制

$1 \leq M \leq 2000$　字符串 $S$ 的长度
$1 \leq N \leq 2000$　字符串 $T$ 的长度

评分标准

在评分数据中，占分值 20% 的部分满足 $M \leq 10$, $N \leq 10$。
在评分数据中，占分值 50% 的部分满足 $M \leq 50$, $N \leq 50$。

翻译由 DeepSeek V3.2 完成