시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 9 6 6 66.667%

문제

情報オリンピック日本委員会では,台湾大会に向かう選手を応援するために新しい JOI 旗を作成することにした.

JOI 旗は,正方形が縦に M 行,横に N 列並んだ形をしており,各正方形には J,O,I のいずれかの文字が 1 つずつ書かれている.

JOI 旗の例

情報オリンピック日本委員会は JOI 旗とは別に JOI 紋章というものを決めている.JOI 紋章は,正方形が縦に 2 行,横に 2 列並んだ形をしており,各正方形には J,O,I のいずれかの文字が 1 つずつ書かれている.

JOI 紋章の例

JOI 旗に含まれる JOI 紋章の個数とは,JOI 旗に含まれる縦 2 行,横 2 列の領域のうち,その領域の J,O,I の配置が JOI 紋章と (回転や裏返しをせずに) 一致しているものの個数のことである.条件を満たす縦2 行,横 2 列の領域同士が重なっていてもそれらを別々に数えるものとする.

情報オリンピック日本委員会は古い JOI 旗と 1 枚の白紙を持っている.白紙は JOI 旗を構成する正方形1 個分の大きさで,J,O,I のうち好きな 1 文字を書き込むことができる.情報オリンピック日本委員会は以下のいずれか 1 つの操作をして,新しい JOI 旗を作成することにした.

古い JOI 旗に対して何も操作せず,そのまま新しい JOI 旗とする.白紙は使用しない.
白紙に 1 文字書き込み,古い JOI 旗のいずれかの正方形に重ねて貼り付けることで古い JOI 旗のうち 1 箇所を変更する.変更後の JOI 旗を新しい JOI 旗とする.

情報オリンピック日本委員会は新しい JOI 旗に含まれる JOI 紋章の個数をできるだけ多くしたいと思っている.あなたは新しい JOI 旗に含まれる JOI 紋章の個数の最大値を求めることになった.

古い JOI 旗と JOI 紋章の情報が与えられたとき,新しい JOI 旗に含まれる JOI 紋章の個数の最大値を求めるプログラムを作成せよ.

입력

標準入力から以下のデータを読み込め.

  • 1 行目には 2 個の整数 M, N が空白を区切りとして書かれている.これは JOI 旗が正方形が縦に M行,横に N 列並んだ形であることを表している.
  • 続く M 行の各行には,それぞれ N 文字からなる文字列が書かれている.各文字は J,O,I のいずれかであり,M 行のうち上から i 行目 (1 ≤ i ≤ M) に書かれている文字列の左から j 文字目 (1 ≤ j ≤ N)は古い JOI 旗の上から i 行目,左から j 列目の正方形に書かれている文字を表す.
  • 続く 2 行の各行には,それぞれ 2 文字からなる文字列が書かれている.各文字は J,O,I のいずれかであり,2 行のうち上から i 行目 (1 ≤ i ≤ 2) に書かれている文字列の左から j 文字目 (1 ≤ j ≤ 2) はJOI 紋章の上から i 行目,左から j 列目の正方形に書かれている文字を表す.

すべての入力データは以下の条件を満たす.

  • 2 ≤ M ≤ 1 000.
  • 2 ≤ N ≤ 1 000.

 

출력

標準出力に,新しい JOI 旗に含まれる JOI 紋章の個数の最大値を表す整数を 1 行で出力せよ.

 

예제 입력

3 5
JOIJO
IJOOO
IIJIJ
JO
IJ

예제 출력

3

예제 입력 2

2 6
JOJOJO
OJOJOJ
OJ
JO

예제 출력 2

2

예제 입력 3

2 2
JI
IJ
JJ
JJ

예제 출력 3

0

힌트

古い JOI 旗と JOI 紋章は問題文中の例の通りである.上から 2 行目,左から 4 列目の正方形を白紙を用いて J に変更すると,次のような形になる.

JOI 旗の 1 箇所を変更した例

このように変更した後の JOI 旗には次に示す 3 箇所に JOI 紋章と同じ配置の領域がある.

JOI 紋章と同じ配置の領域

JOI 紋章と同じ配置の領域が 4 箇所以上となる新しい JOI 旗は存在しないので,新しい JOI 旗に含まれる JOI 紋章の個数の最大値は 3 である.