配点: 100 点
日本信息奥林匹克委员会决定制作一面新的 JOI 旗帜,以支持前往台湾奥运会的运动员。
JOI 标志是一个垂直的正方形。 M 线,水平 N 排成一排,每个方格都有一个 J,O,I 中的任意字符 1 一一写着。

日本信息奥林匹克委员会已决定将 JOI 标志与 JOI 旗帜分开。 JOI标志是一个垂直的正方形。 2 线,水平 2 排成一排,每个方格都有一个 J,O,I 中的任意字符 1 一一写着。

JOI标志中包含的JOI标志的数量是JOI标志中包含的JOI标志的数量。
列中区域的 2 行,横 2 。
这是位置与 JOI 标志相匹配的 J,O,I 的数量(不旋转或翻转)。符合条件的垂直 2 行,横 2 即使列中的区域重叠,也会单独计算。
日本信息奥林匹克委员会
我有 1 张空白纸。空白方块是构成 JOI 标志的方块。
大小为 1 ,J,O,I 随你喜欢 1 您可以写入字符。日本信息奥林匹克委员会是以下组织之一 1 我决定通过执行两个操作来创建一个新的 JOI 标志。
- 不要对旧的 JOI 标志执行任何操作,并将其用作新的 JOI 标志。请勿使用空白纸。
- 空白纸 1 通过将文本粘贴到旧 JOI 标记的任何方块上,在任何旧 JOI 标记上写入文本。 1 更改位置。将改变后的JOI标志设置为新的JOI标志。
日本信息奥林匹克委员会希望在新的 JOI 旗帜上包含尽可能多的 JOI 标志。您想要找到新 JOI 标志中可以包含的 JOI 标志的最大数量。
課題
给定旧 JOI 标志和 JOI 标志的信息,编写一个程序来计算新 JOI 标志中包含的 JOI 标志的最大数量。
入力
从标准输入读取以下数据。
- 1 行中, 2 整数 M, N 以空格作为分隔符。这是一个带有垂直正方形的 JOI 旗帜 M 线,水平 N 这表明它们排成一排。
- 继续 M 行的每一行包含 N 写入一串字符。每个字母都是
J,O,I,M 从行顶部开始 从 i 行目 (1 \leqq i \leqq M中写入的字符串左侧开始) j 文字目 (1 \leqq j \leqq N) 从旧的 JOI 标志上方 i 线,从左起 j 表示列中方框中写入的字符。 - 继续 2 行的每一行包含 2 写入一串字符。每个字母都是
J,O,I,2 从行顶部开始 从 i 行目 (1 \leqq i \leqq 2中写入的字符串左侧开始) j 文字目 (1 \leqq j \leqq 2) 从 JOI 徽章上方 i 线,从左起 j 表示列中方框中写入的字符。
出力
表示新 JOI 标志中包含的 JOI 标志的最大数量的整数被发送到标准输出。 输出为 1 行。
制限
所有输入数据满足以下条件。
- 2 \leqq M \leqq 1\,000.
- 2 \leqq N \leqq 1\,000.
小課題
小課題 1 [30 点]
满足以下条件。
- M \leqq 50.
- N \leqq 50.
小課題 2 [70 点]
没有其他限制。
入力例 1
3 5 JOIJO IJOOO IIJIJ JO IJ
出力例 1
3
旧的 JOI 旗帜和 JOI 标志如问题中的示例所示。从上面 2 线,从左起 4 使用白纸在栏中画出正方形。
如果将其更改为 J ,它将如下所示:

进行这些更改后,JOI 标志应如下所示: 3 有一个区域与JOI标志的布局相同。

与JOI标志相同布局的区域是 没有超过 4 的新 JOI 标志,因此新 JOI 标志中包含的 JOI 标志的最大数量为 3 。
入力例 2
2 6 JOJOJO OJOJOJ OJ JO
出力例 2
2
请注意,可以在不使用空白纸的情况下获得最大值。
入力例 3
2 2 JI IJ JJ JJ
出力例 3
0
在此输入/输出示例中,JOI 标志将出现在任何可能的新 JOI 标志上。 1 不包括在内。