车辆编组问题

问题描述

在IOI国，最近新建了一条铁路。IOI国的列车由多个车辆连接而成，车辆有两种类型：I和O。每种类型的车辆只能与不同类型的车辆连接。另外，由于需要设置驾驶座位，列车的两端车辆必须是类型 I。用一个由表示车辆类型的字符按顺序连接起来的字符串来表示列车，列车的长度即为该字符串的长度。例如，按照顺序连接车辆 IOIOI 可以组成长度为5的列车，而单独的车辆 I 是长度为1的列车。但是，无法按照 OIOI 或 IOOI 的顺序排列车辆以组成列车。

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

在编组列车之前，可以将任意数量的车辆从车库移动到另一个待命轨道上。一旦将车辆移动到待命轨道，就不能再将其用于编组列车。另外，在开始编组列车后，不能将车辆从车库移动到待命轨道。

在编组列车时，不必使用车库中的所有车辆。也就是说，在完成列车编组之后，车库中还剩下未使用的车辆也是可以的。

由于IOI国认为乘坐火车的人非常多，所以希望尽可能编组更长的列车。

这张图对应于示例输入1和输出1。

问题

给定存放在车库中的车辆信息，请编写一个程序，计算能够编组的列车的最大长度。每个车库中的车辆列由仅由两种字符 I 和 O 组成的字符串表示，车库的信息由长度为 M 的字符串 S 和长度为 N 的字符串 T 表示。每个字符表示一个车辆，字符与车辆类型相同。字符串的第一个字符表示离车库入口最近的车辆，末尾的字符表示车库中最靠近车库底部的车辆。

限制条件

$1 \leqq M \leqq 2,000$

$1 \leqq N \leqq 2,000$

输入

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

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

输出

在标准输出中，以一个整数的形式输出能够编组的列车的最大长度。如果无法编组任何列车，请输出0。

评分标准

对于某些评分用例，满足 $M \leqq 10$，$N \leqq 10$。

对于另一些评分用例，满足 $M \leqq 50$，$N \leqq 50$。

示例输入 1

5 5
OIOOI
OOIOI

示例输出 1

7

假设将车库 S 中的第一个车辆和车库 T 中的前两个车辆移动到待命轨道上，在按照顺序从车库 S、车库 S、车库 T、车库 S、车库 S、车库 T、车库 T 取出车辆时，可以编组出长度为 7 的列车 IOIOIOI。

还可以考虑将车库 S 中的第一个车辆和车库 T 中的前两个车辆移动到待命轨道上，并按照顺序从车库 T、车库 T、车库 S、车库 S、车库 T、车库 S、车库 S 取出车辆时，也可以编组出长度为 7 的列车。但是无法编组出比这更长的列车，因此输出结果为 7。

示例输入 2

5 9
IIIII
IIIIIIIII

示例输出 2

1

注意单独由一个车辆组成的列车 I 也满足列车的条件。