「JOI 2013 Final」搭乘 IOI 火车
题目描述
译自 JOI 2013 Final T2「IOI 列車で行こう」
IOI 国正在建造一条新的铁路。IOI 国的火车都由若干车厢组成。车厢有 I,O 两种。不同种类的两车厢间可以连接。由于火车中需要设置司机的车厢，所以火车两端的车厢必须为种类为 I 的车厢。火车各车厢的种类由一个字符串表示，字符串各字符的顺序就是火车车厢的顺序，列车的长等于这个字符串的长度。例如，以 IOIOI 的顺序连接车厢组成的火车的长度为 $$5$$ ，又例如车厢 I 自身是一辆长度为 $$1$$ 的火车。以 OIOI 的顺序或 IOOI 的顺序连接车厢不能组成一列火车。
若干车厢储存在两个车库中。每个车库中的车厢排成一列。在组装火车时，车厢将从车库中运出到车库前进行连接。从车库中运出的车厢将和离车库最近的车厢进行连接。从两个车库中运出车厢的顺序可以自由决定。
组装火车前，可以将车库中的一些车厢移至备用铁路。被移至备用铁路的车厢将不能参与之后的火车组装。另外，一旦火车组装开始，就不能再将车厢移至备用铁路。
组装火车不需要用尽车库中的所有车厢。也就是说，火车组装完成后，即使车库内仍剩有车厢也没关系。
由于 IOI 国乘坐火车的人特别多，所以需要组装尽量长的火车。
图：在组装火车的过程中，不能从车库向备用铁路运送车厢。此图对应输入输出样例 1 。
任务
给出车库中存储的车厢的情况，请编写程序求出能够组成的火车的最大长度。每个车库所储存的车厢的排列由一个字符串表示，此字符串中每个字符为 I 或 O 。给出两个车库的情况，分别为长为 $$M$$ 的字符串 $$S$$ 及长为 $$N$$ 的字符串 $$T$$ ，每个字符表示一个车厢的种类。字符串的第一个字符表示离车库入口最近的车厢，字符串的最后一个字符表示车库最深处的车厢。
输入格式
输入标准如下：
- 第一行为两个以空格分开的整数 $$M,N$$；
- 第二行为字符串 $$S$$；
- 第三行为字符串 $$T$$ 。
输出格式
输出一行一个整数：表示可以组装出的火车的最大长度。当不能组装出符合条件的火车时输出 $$0$$。
样例 1
输入
5 5
OIOOI
OOIOI
输出
7
解释
我们用 $$S$$ 表示字符串 $$S$$ 所表示的车库，用 $$T$$ 表示字符串 $$T$$ 所表示的车库。此时，如果将车库 $$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
输出
1
解释
可以组成长为 $$1$$ 的火车 I 。
数据范围与提示
对于 $$20%$$ 的分值：
对于 $$50%$$ 的分值：
对于 $$100%$$ 的分值：