P15811 [JOI 2014 Final] JOI Badge / JOI Emblem

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.

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 one line to standard output containing one integer, which is the maximum number of **JOI emblems** contained in the new **JOI** flag.

### 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