估计人数

题目描述

给定一个 N × M 的方格矩阵，矩阵中每个方格标记 0 或者 1 代表这个方格是不是有人踩过。

已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。

走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 1，包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘。

请你计算至少有多少人在矩阵上走过。

输入格式

输入第一行包含两个整数 N、M。

以下 N 行每行包含 M 个整数 (0/1)，代表方格矩阵。

输出格式

输出一个整数代表答案。

测试样例1

Input：

5 5

00100

11111

00100

11111

00100

Output：

3

1

2

3

4

5

6

7

8

9

10

评测用例规模与约定

对于所有评测用例，1 ≤ N, M ≤ 20，标记为 1 的方格不超过 200 个。