配点: 100 点
在 IOI 国,这次新建了铁路。IOI 国行驶的列车是由若干车厢连接而成的,车厢中 I,O 的 2 每个车厢只能与不同种类关系的车厢连接。此外,为了在铁路上设置驾驶室,列车两端的车厢是种类 I 。假设一列火车由一串代表车辆类型的字符串按顺序连接表示,火车的长度就是该字符串的长度。例如,
当按照 IOIOI 的顺序连接车辆时,长度 5 可以组织火车,可以组织车辆 I 是单独的长度
这是 1 火车。车辆 OIOI 呀
即使您按照 IOOI 之类的顺序排列火车,也无法组织火车。
一些车辆 2 它存放在两个车库中。每个车库内,车辆都排成一排。编组时,车辆从车辆段取出并在车辆段前连接。只有距离车库入口最近的车辆才能被带出车库,但车辆的取出顺序是自由的。
在形成火车之前,您可以根据需要从车库取出任意数量的车厢,并将它们移动到另一条候车轨道上。一旦车辆被移动到候车轨道上,以后就不能再用来组成火车了。此外,一旦火车组装完毕,在组装完成之前,不可能将车辆从车辆段移至等待轨道。
编组列车时,无需使用车辆段内的所有车厢。换句话说,列车组装完毕后,车段内是否还有未使用的车辆也没有关系。
由于认为IOI国家乘坐火车的人数较多,因此我们希望尽可能长时间地组织火车。

課題
编写一个程序,根据仓库中存储的车辆信息,计算可以形成的火车的最大长度。每个车库存放的车辆行数是 2 字符类型
由仅由 I,O 组成的字符串表示,2 每个车库信息都有长度 M 字符串 S 和长度
它被给出为 N 字符串 T 。每个字母 1 代表一辆车,其字符与车型相同。字符串的 1 第一个字母代表距离车库入口最近的车辆,最后一个字母代表车库内最远的车辆。
制限
| 1 \leqq M \leqq 2\,000 | 文字列 S 长度 |
| 1 \leqq N \leqq 2\,000 | 文字列 T 长度 |
入力
从标准输入读取以下数据。
- 1 在线 写在方格 M, N 用空格分隔。
- 2 行是一个字符串 写入 S 。
- 3 行是一个字符串 写入 T 。
出力
表示可组装火车最大长度的整数被发送到标准输出。 输出为 1 行。火车 1 如果您无法组织 输出0 。
採点基準
评分数据中,分配的分数 20 对于%,M \leqq 10,N \leqq 10 满意。 设
评分数据中,分配的分数 50 对于%,M \leqq 50,N \leqq 50 满意。 设
入力例 1
5 5 OIOOI OOIOI
出力例 1
7
S 代表的车库为车库S,并且
设T 代表的车库为车库T。此时,例如第一个 1 车辆,从车库 T 出发 2 将车辆取出等待后,如果按车库S、车库S、车库T、车库S、车库S、车库T、车库T的顺序取出车辆,则长度 7 火车 IOIOIOI 可以组织。
此外,第一个 1 车辆,从车库 T 出发 2 取出车辆并等待后,您还可以按以下顺序取出车辆:车库T、车库T、车库S、车库S、车库T、车库S、车库S。 7 火车可以组装。不可能组织比这更长的火车。 输出 7 。
入力例 2
5 9 IIIII IIIIIIIII
出力例 2
1
1 仅由一辆车组成的火车
请注意, I 也满足成为火车的条件。