题目描述

给定一个由 J、O、I 组成的 $N \times M$ 网格，以及一个 $2 \times 2$ 的纹章。

定义一个 $2 \times 2$ 子矩阵与纹章匹配，当且仅当该子矩阵的四个字符与纹章完全一致（不允许旋转或翻转）。

现在你可以进行 至多一次 操作：

• 将网格中任意一个位置的字符修改为 J、O、I 中任意一个。

请你求出经过 至多一次 修改后，网格中与纹章匹配的 $2 \times 2$ 子矩阵的最大数量。

注意：不同的子矩阵即使有重叠，也需要分别计数。

输入格式

第一行两个整数 $N,M$。

接下来 $N$ 行，每行一个长度为 $M$ 的字符串，表示初始网格。

接下来 $2$ 行，每行一个长度为 $2$ 的字符串，表示纹章。

输出格式

输出一个整数，表示答案。

3 5
JOIJO
IJOOO
IIJIJ
JO
IJ

3

样例 1 说明

将第 $2$ 行第 $4$ 列修改为 J 后，可以得到 $3$ 个匹配的 $2 \times 2$ 子矩阵。

2 6
JOJOJO
OJOJOJ
OJ
JO

2

样例 2 说明

不进行任何修改是最优的方案。

2 2
JI
IJ
JJ
JJ

0

4 10
OJOOIIJJOO
JIIJOJJOIJ
JJIOIJIJJJ
JOJJIIJIOI
JI
JO

1

提示

数据范围

对于所有数据：

• $2 \le N,M \le 1000$