题目描述

有一个 $H \times W$ 的网格，共有 $H$ 行 $W$ 列。用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子。每个格子的状态用字符 $C_{i,j}$ 表示，$C_{i,j} = '.'$ 表示 $(i,j)$ 是空格子，$C_{i,j}$ = '#' 表示 $(i,j)$ 是墙。

小高将在这个网格上行走。当他在 $(i,j)$ 时，他可以移动到 $(i,j+1)$ 或 $(i+1,j)$。但是，他不能走出网格或进入墙格子。当无法继续移动时，小高将停止。

小高从 $(1,1)$ 开始行走，在他停止之前最多可以经过多少个格子?

输入格式

输入按以下格式从标准输入给出：

$H$ $W$

$C_{1,1}$ ... $C_{1,W}$

$\vdots$

$C_{H,1}$ ... $C_{H,W}$

输出格式

输出所求答案。

样例

3 4
.#..
..#.
..##

4

1 1
.

1

5 5
.....
.....
.....
.....
.....

9

样例1解释

例如，通过 $(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (3,2)$ 的路径，小高可以经过 4 个格子。
他无法经过 5 个或更多格子，所以应输出 4。

数据范围

• $1 \leq H, W \leq 100$, $H$ 和 $W$ 是整数
• $C_{i,j} = '.'$ 或 C_{i,j} = # $(1 \leq i \leq H, 1 \leq j \leq W)$, $C_{1,1} = '.'$。

来源

• AtCoder ABC232D