NC53183. 搭乘 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，每个字符表示一个车厢的种类。字符串的第一个字符表示离车库入口最近的车厢，字符串的最后一个字符表示车库最深处的车厢。
若干车厢储存在两个车库中。每个车库中的车厢排成一列。在组装火车时，车厢将从车库中运出到车库前进行连接。从车库中运出的车厢将和离车库最近的车厢进行连接。从两个车库中运出车厢的顺序可以自由决定。
组装火车前，可以将车库中的一些车厢移至备用铁路。被移至备用铁路的车厢将不能参与之后的火车组装。另外，一旦火车组装开始，就不能再将车厢移至备用铁路。
组装火车不需要用尽车库中的所有车厢。也就是说，火车组装完成后，即使车库内仍剩有车厢也没关系。
由于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 。