AT_joi2014ho1.JOI 紋章 (JOI Emblem)

日本信息奥林匹克委员会决定为前往台湾参加比赛的选手们制作一面新的 JOI 旗帜。

JOI 旗帜由纵向 $M$ 行、横向 $N$ 列排列的正方形组成，每个正方形上写有 J、O、I 中的一个字母。

JOI 旗帜示例

日本信息奥林匹克委员会还定义了名为 JOI 徽章的图案。JOI 徽章由纵向 $2$ 行、横向 $2$ 列排列的正方形组成，每个正方形上同样写有 J、O、I 中的一个字母。

JOI 徽章示例

JOI 旗帜中包含的 JOI 徽章的个数，指的是 JOI 旗帜中所有纵向 $2$ 行、横向 $2$ 列的区域中，与 JOI 徽章的字符排列（不进行旋转或翻转）完全一致的区域的数量。即使这些区域彼此重叠，也要分别计数。

日本信息奥林匹克委员会拥有一面旧的 JOI 旗帜和一张白纸。白纸的大小与 JOI 旗帜中的一个正方形相同，可以在上面写入 J、O、I 中任意一个字母。委员会可以通过以下两种方式之一制作新的 JOI 旗帜：

• 对旧的 JOI 旗帜不做任何操作，直接作为新的 JOI 旗帜。此时不使用白纸。
• 在白纸上写入一个字母，并将其覆盖在旧 JOI 旗帜的任意一个正方形上，从而修改该位置的字符。修改后的 JOI 旗帜即为新的 JOI 旗帜。

日本信息奥林匹克委员会希望新的 JOI 旗帜中包含尽可能多的 JOI 徽章。你的任务是求出新的 JOI 旗帜中 JOI 徽章的最大数量。

从标准输入读取以下数据。

• 第 $1$ 行包含两个整数 $M,\ N$，表示 JOI 旗帜为纵向 $M$ 行、横向 $N$ 列的正方形排列。
• 接下来的 $M$ 行，每行包含 $N$ 个字符，分别为 J、O、I 之一。第 $i$ 行第 $j$ 个字符表示旧 JOI 旗帜第 $i$ 行第 $j$ 列的字符。
• 接下来的 $2$ 行，每行包含 $2$ 个字符，分别为 J、O、I 之一。第 $i$ 行第 $j$ 个字符表示 JOI 徽章第 $i$ 行第 $j$ 列的字符。

输出一个整数，表示新的 JOI 旗帜中 JOI 徽章的最大数量。

任务

给定旧 JOI 旗帜和 JOI 徽章的信息，编写程序求出新的 JOI 旗帜中 JOI 徽章的最大数量。

限制

所有输入数据满足以下条件：

• $2 \leq M \leq 1\,000$。
• $2 \leq N \leq 1\,000$。

子任务

子任务 1 [30 分]

满足以下条件：

• $M \leq 50$。
• $N \leq 50$。

子任务 2 [70 分]

无额外限制。

样例解释 1

旧的 JOI 旗帜和 JOI 徽章如题目中的示例所示。将第 $2$ 行第 $4$ 列的正方形用白纸改为 J 后，旗帜如下所示。
修改了一个位置后的 JOI 旗帜
此时，新的 JOI 旗帜中有如下 $3$ 个区域与 JOI 徽章完全一致。
与 JOI 徽章一致的区域
不存在包含 $4$ 个或更多 JOI 徽章的新 JOI 旗帜，因此最大数量为 $3$。

样例解释 2

注意，有时即使不使用白纸也能得到最大值。

样例解释 3

对于本样例，无论如何修改新的 JOI 旗帜，都无法包含任何一个 JOI 徽章。

由 ChatGPT 4.1 翻译