该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

吉祥是一个喜欢探险的小机器人。今天，它来到了一个神秘的迷宫。

题目描述

这个迷宫由一个$N×M$的网格组成，每个网格要么是空地（用.表示），要么是障碍物（用#表示）。吉祥从左上角($1, 1$)出发，希望到达右下角($N, M$)。

吉祥每次可以向上、下、左、右四个方向移动一格，但不能穿过障碍物。为了增加趣味性，迷宫的设计者在某些空地上放置了能量宝石（用*表示）。当吉祥经过一个能量宝石时，它会获得$1$点能量。

吉祥想知道，从起点到终点的所有可能路径中，能够获得的最大能量值是多少。注意：每条路径经过同一个能量宝石多次时，只能获得一次能量。

输入格式

第一行包含两个整数$N$和$M$，表示迷宫的行数和列数。 接下来$N$行，每行包含$M$个字符，描述迷宫的地图。

输出格式

输出一个整数，表示吉祥从起点到终点能够获得的最大能量值。如果无法到达终点，输出-1。

输入输出样例 #1

输入 #1

3 3
.*.
...
*.*

输出 #1

3

说明/提示

数据范围：

对于100%的数据：1 ≤ N, M ≤ 100。