Chocolate

Time Limit : 2 sec, Memory Limit : 131072 KB

C - チョコレート

目の前に 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番目のピースが甘いことを表わしている.

出力形式

食べることのできる甘いピースの個数の最大値を一行に出力せよ.

制約

  • 1 \leq N,M \leq 100
  • 0 \leq a_{ij} \leq 1
  • 入力値はすべて整数である.

入出力例

入力例1

2 3
1 1 1
1 1 1

出力例1

5

入力例2

4 2
1 0
0 1
0 1
0 1

出力例2

8

Source: Kyoto University Programming Contest 2013 , Kyoto, Japan, 2013-07-06
http://www.kupc.jp/
http://kupc2013.contest.atcoder.jp/