AT_joi2013ho2.IOI 列車で行こう (Take the 'IOI' train)

在 IOI 国，最近新建了一条铁路。运行在 IOI 国铁路上的列车由若干节车厢连接而成，车厢有两种类型，分别用 I 和 O 表示。每节车厢只能与不同类型的车厢相连。此外，由于需要设置驾驶室，列车两端的车厢必须是 I 类型。列车可以用表示车厢类型的字符串依次连接而成，列车的长度即为该字符串的长度。例如，依次连接 IOIOI 可以组成一列长度为 $5$ 的列车，单独的 I 车厢也可以视为长度为 $1$ 的列车。像 OIOI 或 IOOI 这样的顺序无法组成有效的列车。

有若干车厢分别存放在两个车库中。每个车库中的车厢按一列顺序排列。组装列车时，可以从车库中取出车厢，在车库前依次连接。每次只能从每个车库最靠近入口的那节车厢取出，但可以自由选择从哪个车库取车厢的顺序。

在组装列车之前，可以任意多地将车厢从车库取出，放到备用轨道上。被移到备用轨道上的车厢之后不能再用于组装列车。此外，一旦开始组装列车，在组装完成之前，不能再将车厢从车库移到备用轨道。

组装列车时，不需要用完所有车库中的车厢。也就是说，组装完成后，车库中可以剩下未使用的车厢。

由于 IOI 国乘坐铁路的人非常多，因此希望组装出尽可能长的列车。

图为正在组装列车的过程，此时不能再将车厢移到备用轨道。该图对应输入输出样例 $1$。

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

• 第 $1$ 行包含两个用空格分隔的整数 $M,\ N$。
• 第 $2$ 行包含字符串 $S$。
• 第 $3$ 行包含字符串 $T$。

输出一个整数，表示能够组装出的列车的最大长度。如果无法组装出任何列车，则输出 $0$。

任务

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

限制

$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$。

样例解释 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 也满足列车的条件。

由 ChatGPT 4.1 翻译