P15807 [JOI 2013 Final] 搭乘 IOI 火车 / Take the IOI train

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

### 样例解释 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 完成