JOI 徽章

题号：NC53177
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

译自 JOI 2014 Final T1「JOI 紋章」

日本信息学奥赛委员会为了应援将要去台湾参加IOI的选手们，打算制作一面新的JOI旗帜。JOI旗帜为由M行N列的 $M \times N$ 个正方形组成的图形，每个正方形里写有J,O,I中任一字母。

日本信息学奥赛委员会还决定制作JOI徽章。JOI徽章为由2行2列的4个正方形组成的图形，每个正方形里写有J,O,I中任一字母。

JOI旗帜中所含J

OI徽章的个数的意思是，与JOI徽章相同（不允许翻转或旋转）的JOI旗帜中的 $2 \times2$ 区域的个数。
现在日本信息学奥赛委员会拥有一张旧的JOI旗帜和一张白纸。这张白纸的大小和一个构成JOI旗的正方形的大小相同。可以在这张白纸上写上J,O,I中任一字母。日本信息学奥赛委员会将进行以下任意一种操作来制作新的JOI旗帜。

不进行任何操作，直接把旧的旗帜当新的用。不使用白纸。
在白纸上写下一个字母，将白纸覆盖在旧的JOI旗帜的任意一个正方形上（也就是变更旧的JOI旗帜的一个正方形的字母）。

日本信息学奥赛委员会想让新的JOI旗帜所含的JOI徽章的数量尽可能多。请求出新的JOI旗帜所含的JOI徽章的个数的最大值。
任务
给出旧的JOI旗帜和JOI徽章的情况，请求出新的JOI旗帜所含的JOI徽章的个数的最大值。

输入描述:

输入标准如下：
第一行为两个以空格分开的整数M,N。表示旧的JOI旗帜是由M行N列的M×N个正方形组成的图形。
接下来的M行，每行为含有N个字符的字符串。每个字符为J,O,I中的一个。这M行中的第行中从左数第个字符表示旧的JOI旗帜上的第i行第j列的正方形中所写的字符。
接下来的2行，每行为含有2个字符的字符串。每个字符为J,O,I中的一个。这2行中的第行中从左数第个字符表示JOI徽章上的第i行第j列的正方形中所写的字符。

输出描述:

输出一行一个整数：表示新的JOI旗帜所含的JOI徽章的个数的最大值。

示例1

输入

复制

3 5
JOIJO
IJOOO
IIJIJ
JO
IJ

输出

复制

说明

旧的JOI旗帜和JOI徽章和题目描述中的例子一样。从上面起第2行中，从左起第4列的正方形中的字符用白纸覆盖从而变为'J'。
像这样变化后的JOI旗帜含3个JOI徽章。
不存在能够包含4个JOI徽章的新的JOI旗帜。所以新的JOI旗帜所含的JOI徽章的个数的最大值为3。

示例2

输入

复制

2 6
JOJOJO
OJOJOJ
OJ
JO

输出

复制

说明

请注意：存在不使用白纸而能达到最大值的情况。

示例3

输入

复制

2 2
JI
IJ
JJ
JJ

输出

复制

说明

在输入样例3的情况下，对于任何可能的新的JOI旗帜，都不可能含有1个JOI徽章。

备注:

对于的分值：


对于的数据，满足以下条件。


CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2756