就在你面前 有一块由 M \times N 块制成的巧克力棒。 片有两种:甜片和辣片,你想吃尽可能多的甜片。
但是,如何吃巧克力是有规则的,必须遵守以下规则。
- 为了吃掉某个棋子,它的正上方不能有相邻的棋子,此外,该棋子的左侧或右侧至少不能有任何棋子。
例如,巧克力形状如图所示,接下来可以吃红色的那块。
[原图]
另外,奇怪的是,当你吃掉某一块时,上、下、左、右与该块相邻但尚未被吃掉的块的味道会发生变化。 (甜的变辣,辣的变甜)
巧克力吃得好,能吃多少颗甜品?
入力形式
输入按以下格式给出。
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