JOI 2008-2009 予選問題４

冬の寒いある日，JOI太郎君は広場にはった薄氷を割って遊ぶことにした．広場は長方形で，東西方向に m 個，南北方向に n 個，つまり， m × n の区画に区切られている．また，薄氷が有る区画と無い区画がある． JOI太郎君は，次のルールにしたがって，薄氷を割りながら区画を移動することにした．

薄氷があるどの区画からも薄氷を割り始めることができる．
東西南北のいずれかの方向に隣接し，まだ割られていない薄氷のある区画に移動できる．
移動した先の区画の薄氷をかならず割る．

JOI太郎君が薄氷を割りながら移動できる区画数の最大値を求めるプログラムを作成せよ．ただし， 1 ≦ m ≦ 90，1 ≦ n ≦ 90 である．与えられる入力データでは，移動方法は20万通りを超えない．

入力

入力はn+2行ある． 1 行目には整数 m が書かれている． 2 行目には整数 n が書かれている． 3 行目から n+2 行目までの各行には、0 もしくは 1 が，空白で区切られて m 個書かれており，各区画に薄氷があるか否かを表している．北から i 番目，西からj番目の区画を (i,j) と記述することにすると (1 ≦ i ≦ n, 1 ≦ j ≦ m)，第 i+2 行目の j 番目の値は，区画 (i,j) に薄氷が存在する場合は 1 となり，区画 (i,j) に薄氷が存在しない場合は 0 となる．

出力

入出力例

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．

入力例１	入力例２
3 3 1 1 0 1 0 1 1 1 0	5 3 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1

出力例１	出力例２
5	5
入力例1に対して，最大値を与える移動方法の例	入力例2に対して，最大値を与える移動方法の例

問題

入力

出力

入出力例

テストデータ