Description

小黄最近在玩一款 2DRPG 游戏《魔〇少女苍〇星》。在游戏的一个迷宫中，用一个 $n * m$ 大小的字符矩阵来表示迷宫的地图，字符矩阵中包含以下类型的字符：

\begin{itemize} \item $`\#'$：表示迷宫的墙体，小黄无法操纵主角苍〇星走到迷宫墙体的位置。字符矩阵的外部也视为迷宫的墙体，苍〇星无法进入。迷宫墙体以外的部分保证连通。 \item $`.'$：表示迷宫的路径，小黄可以操纵主角苍〇星在迷宫的路径上任意移动。 \item $`+'$：表示主角苍〇星的初始位置。在游戏开始时，苍〇星站在 $`+'$ 的位置。在苍〇星移动后，$`+'$ 的位置和普通的迷宫路径没有区别。$`+'$ 的位置在一个迷宫中只有一个。 \item $`-'$：表示本层迷宫的终点。苍〇星可以从迷宫的路径移动到迷宫的终点。苍〇星到达终点即可到达下一层迷宫，这也意味着本层迷宫结束。$`-'$ 的位置在一个迷宫中只有一个。 \item $``123456789''$：如果出现这个字符串中的任意一个字符（这个字符表示了一个非 $0$ 数字），就意味着该格点存在一个魔物。魔物拥有一个血量属性，魔物的初始血量即为那个字符表示的数。例如，$`2'$ 表示该格点存在一个初始血量为 $2$ 的魔物。苍〇星可以对魔物造成伤害，若一个魔物的血量小于等于 $0$，则该魔物死亡，原本是这个魔物的格点不再认为存在魔物，成为一个普通的迷宫路径。 \item $`*'$：表示一个特殊的装置``瘴气之核''。瘴气之核可以视为迷宫的路径，但特殊的是，当苍〇星第一次移动到瘴气之核的位置时，会自动摧毁瘴气之核。摧毁瘴气之核将导致本层所有魔物恢复到初始状态------即已经死亡的魔物将复活，且所有魔物的血量变成初始血量------然后使得本层迷宫中的所有魔物血量变为一半。瘴气之核被摧毁后，依然可以当作迷宫的路径来移动，只是再次进入不会有额外效果。$`*'$ 的位置在一个迷宫中只有一个。 \end{itemize}

小黄每次可以操纵主角苍〇星在迷宫中在以下行动中选择一个执行：

\begin{itemize} \item 若苍〇星上下左右四个方向紧邻当前格点的位置存在迷宫的路径，则可以移动到该路径上。正式地说，若苍〇星当前的位置为 $(x, y)$，则苍〇星可以移动到 $(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)$ 中任意一个是迷宫的路径的位置。 \item 若苍〇星上下左右四个方向紧邻当前格点的位置存在魔物，则可以选择其中一个魔物，对其造成 $1$ 点伤害。正式地说，若苍〇星当前的位置为 $(x, y)$，则苍〇星在 $(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)$ 中选择一个魔物。对其造成 $1$ 点伤害。 \end{itemize}

小黄已经通关过一次《魔〇少女苍〇星》，现在正在打二周目全收集，因此不想浪费太多时间，只打算快速通过每一个迷宫。对于题目给出的迷宫，请你告诉小黄操纵苍〇星从初始位置到本层迷宫的终点所需的最小的行动执行次数。

Format

Input

第一行包含两个整数 $n, m\ (2 \leq n, m \leq 1000)$，表示迷宫的行数和列数。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串。字符串的含义如题所示。

保证一个迷宫中 $``+-*''$ 三种字符各有且仅有一个。且保证迷宫墙体以外的部分连通。

Output

输出一个整数，表示小黄操纵苍〇星从初始位置到本层迷宫的终点所需的最小的行动执行次数。

Samples

4 6
###+11
###111
66655*
-#####

28

6 6
*99999
999999
99##99
99##99
999999
+9999-

41

6 6
*99999
.99999
.9##99
.9##99
.99999
+9999-

35

Limitation

1s, 1024KiB for each test case.