题目描述

面条老师 最近在玩一个游戏，这个游戏地图由一个 $n * m$ 的矩形地图构成，每个坐标都对应一个格子。

每个格子中可能存在怪物，也可能是空地，玩家需要在地图上建造防御塔来击杀怪物。

但是在这个游戏中，一个防御塔只能朝 上下左右 四个方向其中一个发射激光（攻击距离无限），当防御塔选择攻击方向以后就不允许修改了

现在 面条老师 的新手任务是选择一个空地建造一座防御塔，要求这座防御塔能击杀至少一个怪物

面条老师 希望能够完美完成新手任务，所以他想知道有多少种不同的方案来建造这座防御塔？

P.S. 同一个格子不同方向的防御塔也被认为是不同的方案

输入格式

第一行输入两个空格隔开的整数 $n,m$。

接下来 $n$ 行，每行输入 $m$ 个整数，每个整数是 $0$ 或者 $1$。

$0$ 表示这个格子是空地，$1$ 表示这个格子上有一个怪物。

输出格式

输出一个整数，表示合适的摆放位置总数。

2 4
0 1 0 0
1 0 1 0

9

4 4
0 0 1 0
1 0 1 1
1 0 0 0
0 0 0 0

15

样例解释 1

在 $(1, 1)$ 位置，防御塔向下和向右攻击都可以击杀怪物，有 $2$ 种方案。

在 $(1, 3)$ 位置，防御塔向左和向下攻击都可以击杀怪物，有 $2$ 种方案。

在 $(1, 4)$ 位置，防御塔向左攻击可以击杀怪物，有 $1$ 种方案。

在 $(2, 2)$ 位置，防御塔向左，向右和向上攻击可以击杀怪物，有 $3$ 种方案。

在 $(2, 4)$ 位置，防御塔向左攻击可以击杀怪物，有 $1$ 种方案。

所以总共有 $9$ 种方案。

数据规模与约定

对于 $30\%$ 的数据：$n = 1, 1 \le m \le 100$。

对于 $90\%$ 的数据：$1 \le n, m \le 100$。

对于 $100\%$ 的数据：$1 \le n, m \le 1000$。

大样例

大样例下载