题目描述

译自 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$ 的火车的情况。

5 9
IIIII
IIIIIIIII

1

可以组成长为 $1$ 的火车 I 。

数据范围与提示

对于 $20\%$ 的分值：

• $M \leq 10 , N \leq 10$

对于 $50\%$ 的分值：

• $M \leq 50 , N \leq 50$

对于 $100\%$ 的分值：

• $1 \leq M \leq 2000 , 1 \leq N \leq 2000$