Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB
縦 H マス、横 W マスのチョコレートがある。各マスはブラックチョコかホワイトチョコである。ブラックチョコ同士、ホワイトチョコ同士は辺を共有しない(つまり、チョコレートは市松模様を形成している)。 各マスごとにチョコレートの濃度が定まっている。チョコレートの例を以下に表す(数字は濃度を表す)。
妹はこのチョコレートから、ある長方形領域を切り出して溶かし、チョコクリームを作成することにした。妹はチョコレートの味にこだわりを持っており、チョコクリームに使用されたブラックチョコとホワイトチョコの濃度の合計値(ただし、それぞれ使用されていない場合は濃度の合計値を 0 として扱うものとする)が等しくなければ気が済まない。
妹は条件を満たす切り出し方のうち、使用するチョコレートのマス数が最大でいくつになるのかが知りたい。
入力は以下の形式で標準入力から与えられる。
H W C_{1,1} C_{1,2} .. C_{1,W} C_{2,1} C_{2,2} .. C_{2,W} : C_{H,1} C_{H,2} .. C_{H,W}
条件を満たす切り出し方が存在するなら、その中で使用するマス数の最大値を、存在しないなら 0
を出力せよ。出力の末尾にも改行を入れること。
3 4 4 6 2 5 3 5 6 7 2 5 5 6
6
下図のように縦 2 マス、横 3 マスの長方形領域を切り出せば、マス数が 6 となり、濃度の合計も 17 ずつと条件を満たす。
2 2 4 0 7 3
4
濃度が 0 である場合が含まれることに注意せよ。
2 3 0 0 0 1 2 3
3
3 3 1 2 3 6 5 4 7 8 9
0
この例において、条件を満たす切り出し方は存在しない。
1 5 0 1 2 3 4
1
ブラックチョコかホワイトチョコの一方のみを切り出す場合でも条件を満たす場合が存在することに注意せよ。