题目描述

设有一个 $m \times n$ 的矩阵，其中每个格子代表一个非负整数价值，部分格子为障碍，无法通过。一个小机器人位于矩阵的左上角 $(1,1)$，目标是移动到右下角 $(m,n)$。机器人每次可以向上、下、左、右四个方向移动一格，不能走出矩阵边界，也不能经过障碍，每个点只能走一次。

请计算小机器人从起点左上角到终点右下角所能获取的最大价值和。如果无法到达终点，输出 -1。

输入格式

第一行包含两个整数 $m$ 和 $n$，表示矩阵的行数和列数。

接下来的 $m$ 行，每行包含 $n$ 个整数，第 $i$ 行第 $j$ 个整数表示矩阵中 $(i,j)$ 位置的内容：

若为 非负整数，表示该位置的价值；

若为 #，表示该位置为障碍，不能经过。

输出格式

输出一个整数，表示从起点 $(1,1)$ 到终点 $(m,n)$ 所能获得的最大价值和；如果无法到达终点，输出 -1。

样例

3 3
1 3 1
# # 1
0 0 1

7

3 3
1 3 1
# # #
0 0 1

-1

数据范围

• $1 ≤ m×n ≤ 25$
• 矩阵中的数值范围为 # 表示障碍，或者 $-1000$ 至 $1000$