情報オリンピック日本委員会では,台湾大会に向かう選手を応援するために新しいJOI 旗を作成することにした.
JOI 旗は,正方形が縦に $M$ 行,横に $N$ 列並んだ形をしており,各正方形には J,O,I のいずれかの文字が1 つずつ書かれている.
情報オリンピック日本委員会はJOI 旗とは別にJOI 紋章というものを決めている.JOI 紋章は,正方形が縦に2 行,横に2 列並んだ形をしており,各正方形にはJ,O,I のいずれかの文字が1 つずつ書かれている.
JOI 旗に含まれるJOI 紋章の個数とは,JOI 旗に含まれる縦2 行,横2 列の領域のうち,その領域のJ,O,I の配置がJOI 紋章と(回転や裏返しをせずに) 一致しているものの個数のことである.条件を満たす縦2 行,横2 列の領域同士が重なっていてもそれらを別々に数えるものとする.
情報オリンピック日本委員会は古いJOI 旗と1 枚の白紙を持っている.白紙はJOI 旗を構成する正方形1 個分の大きさで,J,O,I のうち好きな1 文字を書き込むことができる.情報オリンピック日本委員会は以下のいずれか1 つの操作をして,新しいJOI 旗を作成することにした.
情報オリンピック日本委員会は新しいJOI 旗に含まれるJOI 紋章の個数をできるだけ多くしたいと思っている.あなたは新しいJOI 旗に含まれるJOI 紋章の個数の最大値を求めることになった.
古いJOI 旗とJOI 紋章の情報が与えられたとき,新しいJOI 旗に含まれるJOI 紋章の個数の最大値を求めるプログラムを作成せよ.
標準入力から以下のデータを読み込め.
標準出力に,新しいJOI 旗に含まれるJOI 紋章の個数の最大値を表す整数を1 行で出力せよ.
すべての入力データは以下の条件を満たす.
3 5 JOIJO IJOOO IIJIJ JO IJ
3
古いJOI 旗とJOI 紋章は問題文中の例の通りである.上から2 行目,左から4 列目の正方形を白紙を用いてJ に変更すると,次のような形になる.
このように変更した後のJOI 旗には次に示す3 箇所にJOI 紋章と同じ配置の領域がある.
JOI 紋章と同じ配置の領域が4 箇所以上となる新しいJOI 旗は存在しないので,新しいJOI 旗に含まれるJOI 紋章の個数の最大値は3 である.
2 6 JOJOJO OJOJOJ OJ JO
2
白紙を使用しなくても最大値が得られる場合があることに注意せよ.
2 2 JI IJ JJ JJ
0
この入出力例の場合,考えられるどの新しいJOI 旗においても,JOI 紋章が1 つも含まれない.
問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。