题目描述

Stella 是一个神箭手，不过并不是他自己射箭 —— 在一块 $N \times M$ 的方格空地上有些地方摆有箭塔，其他还有地方有箭靶。每个箭靶有不同的分值，而箭塔的方向为上下左右其中一种，Stella 通过控制箭塔选定目标，然后一起发射击中这些箭靶获取其分数来展现自己的「射箭」技术。现在你需要计算在给定的空地上，Stella 最多能获得多大的分数。

相关的限制如下：

1. 每个箭塔原则上可以选择所指方向上任意一个箭靶，当然也可以选择不攻击。
2. 为保证正常运行，每个箭塔的攻击范围中不会有其他箭塔。
3. 同样为确保正常攻击，所有箭塔的攻击轨迹在地面的投影不能在任意格子相交。

输入格式

第一行两个整数 $N, M$。

接下来 $N$ 行每行 $M$ 个字符，表示每个格子的状态：

1. . 表示空地。
2. A、V、<、> 分别表示朝向上下左右的箭塔。
3. 1 $\sim$ 9 分别表示得分为 $1$ 到 $9$ 的箭靶。

输出格式

输出一行一个整数，表示最大得分。

3 4
.9V.
>..7
.A1.

10

提示

对于 $30\%$ 的数据，$N, M \le 5$。

对于 $100\%$ 的数据，$N, M \le 50$。