目の前に M \times N 個のピースでできた板チョコがある. ピースには甘いピースと辛いピースの2種類があり,できるだけ多くの甘いピースを食べたい.
しかし,板チョコの食べ方にはルールがあり,以下のルールを守らなければならない.
例えば,図のような形のチョコレートでは,赤く色付けされたピースを次に食べることができる.
また奇妙なことに,あるピースを食べるとそのピースの上下左右に隣接していてかつまだ食べられていないピースの味が変化する. (甘いピースは辛く,辛いピースは甘くなってしまう)
上手くチョコレートを食べると最大でいくつの甘いピースを食べることができるだろうか?
入力は以下の形式で与えられる.
M N a_{11} … a_{1N} a_{21} … a_{2N} : a_{M1} … a_{MN}
a_{ij} = 0 のとき上からi番目,左からj番目のピースが辛く, a_{ij} = 1 のとき上からi番目,左からj番目のピースが甘いことを表わしている.
食べることのできる甘いピースの個数の最大値を一行に出力せよ.
2 3 1 1 1 1 1 1
5
4 2 1 0 0 1 0 1 0 1
8