版权声明

本题版权归 XJSOJ 所有。

本题搬运自 XJSOJ CSP-J2 2025 模拟赛，已经得到版权方的搬运许可。

注意

本题需要文件读写（maze.in / maze.out）。

题目描述

现有一个 $n \times m$ 的四连通带障碍网格。

网格中的某些格子放置了金币，当你走到对应格子时，你将可以收集金币。

你想从 $(1, 1)$ 出发，在 $(n, m)$ 停下，问途中最多可以收集多少枚金币？

你可以在经过 $(n, m)$ 后继续收集金币，直到你决定停下。

特别地，如果无法到达 $(n, m)$，输出 $-1$。

输入格式

第一行两个正整数 $n,m\ (1 \le n,m \le 100)$。

下面一个 $n \times m$ 的字符矩阵：

不保证 $(1, 1)$ 和 $(n, m)$ 不是障碍。

每个有金币的格子中有且仅有一枚金币。

输出格式

一行一个整数表示答案。

样例

3 3
.*.
...
*.*

3

3 5
.*.#.
*.#.*
.#.*.

-1

4 4
*.#*
...#
#...
*#.*

2