Problem Description

The Japanese Olympiad in Informatics Committee, in order to cheer for the contestants participating in the Taiwan contest, decided to make a new JOI flag.

The JOI flag is a square grid with $M$ rows and $N$ columns. Each cell contains one character from J, O, I.

:::align{center}

Example of a JOI flag. :::

In addition to the JOI flag, the Japanese Olympiad in Informatics Committee also defines a JOI emblem. A JOI emblem is a square grid with $2$ rows and $2$ columns. Each cell contains one character from J, O, I.

:::align{center}

Example of a JOI emblem. :::

The number of JOI emblems contained in a JOI flag means the number of $2 \times 2$ regions (2 rows and 2 columns) in the flag whose arrangement of J, O, I is exactly the same as the JOI emblem (without rotation or reflection). Even if such $2 \times 2$ regions overlap, they should be counted separately.

The Japanese Olympiad in Informatics Committee has an old JOI flag and a blank sheet of paper. The blank paper is the same size as one cell of the JOI flag, and you can write any one character from J, O, I on it. The committee decides to create a new JOI flag by performing one of the following two actions:

• Do nothing to the old JOI flag and use it directly as the new JOI flag. The blank paper is not used.
• Write one character on the blank paper, then cover and paste it onto any one cell of the old JOI flag, thereby changing exactly one position in the old JOI flag. Use the modified flag as the new JOI flag.

The committee wants the number of JOI emblems contained in the new JOI flag to be as large as possible. You need to find the maximum possible number of JOI emblems contained in the new JOI flag.

Task

Given the information of the old JOI flag and the JOI emblem, write a program to compute the maximum number of JOI emblems contained in the new JOI flag.

Input Format

Read the following data from standard input.

• The first line contains two integers $M, N$ separated by spaces. This means the JOI flag is a grid with $M$ rows and $N$ columns.
• The next $M$ lines each contain a string of length $N$. Each character is one of J, O, I. In the $i$-th line from the top ($1 \le i \le M$), the $j$-th character from the left ($1 \le j \le N$) represents the character written in the cell at row $i$ from the top and column $j$ from the left of the old JOI flag.
• The next $2$ lines each contain a string of length $2$. Each character is one of J, O, I. In the $i$-th line from the top ($1 \le i \le 2$), the $j$-th character from the left ($1 \le j \le 2$) represents the character written in the cell at row $i$ from the top and column $j$ from the left of the JOI emblem.

Output Format

Output one line to standard output containing one integer, which is the maximum number of JOI emblems contained in the new JOI flag.

3 5
JOIJO
IJOOO
IIJIJ
JO
IJ

3

2 6
JOJOJO
OJOJOJ
OJ
JO

2

2 2
JI
IJ
JJ
JJ

0

Hint

Sample Explanation 1

The old JOI flag and the JOI emblem are the same as the examples in the statement. If you use the blank paper to change the cell at row $2$ from the top and column $4$ from the left to J, it becomes the following:

:::align{center}

Example of changing one position of the JOI flag. :::

In the modified JOI flag, the following $3$ regions have the same arrangement as the JOI emblem:

:::align{center}

Regions that match the JOI emblem arrangement. :::

There is no new JOI flag that contains $4$ or more regions matching the JOI emblem arrangement, so the maximum number of JOI emblems contained in the new JOI flag is $3$.

Sample Explanation 2

Note that sometimes you can obtain the maximum value without using the blank paper.

Sample Explanation 3

For this sample, no JOI emblem is contained in any possible new JOI flag.

Constraints

All input data satisfy the following conditions:

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

Subtasks

Subtask 1 [30 points]

The following conditions hold:

• $M \le 50$
• $N \le 50$

Subtask 2 [70 points]

No additional constraints.

Translated by DeepSeek V3.2.

Translated by ChatGPT 5