JOI emblem

Interview

Time limit1sMemory limit256 MB

Summary

You may change at most one cell of the letter grid, then count how many 2 by 2 blocks match the emblem, and report the largest possible count.

Level: Medium4 of 10
Topics: Brute force, Matrix
Solved: No attempts yet

Problem

The Japan committee for the Olympiad in Informatics is preparing a new JOI flag. The flag is an $M$ by $N$ grid of squares, and each square shows J, O, or I.

The committee also fixed a JOI emblem: a $2$ by $2$ grid of squares with J, O, or I in each cell.

An emblem occurrence in the flag is a $2$ by $2$ region whose four letters match the emblem exactly without rotation or reflection. Overlapping regions are counted separately.

The committee has the old flag and one blank sticker that can cover a single square. The sticker can show any of J, O, or I. Exactly one of these actions is allowed:

Keep the old flag unchanged and do not use the sticker.

Write one letter on the sticker, place it on one square of the old flag, and use the resulting grid as the new flag.

Find the maximum possible number of emblem occurrences in the new flag.

Input

The first line contains $M$ and $N$ . The next $M$ lines are strings of length $N$ over J, O, and I describing the old flag. Row $i$ , column $j$ is the $j$ -th character on the $i$ -th of these lines.

The following two lines are strings of length $2$ over J, O, and I describing the emblem.

Output

Print one integer: the maximum number of emblem occurrences in the new flag.

Constraints

$2 \le M \le 1000$

$2 \le N \le 1000$

Examples3

Example 1
Input
```
3 5
JOIJO
IJOOO
IIJIJ
JO
IJ
```
Expected output
```
3
```
Example 2
Input
```
2 6
JOJOJO
OJOJOJ
OJ
JO
```
Expected output
```
2
```
Example 3
Input
```
2 2
JI
IJ
JJ
JJ
```
Expected output
```
0
```