题目描述

Stella 是一名神箭手，但他并不亲自射箭。在一块 $N \times M$ 的方格空地上，部分格子设有箭塔，其余格子可能设有箭靶。每个箭靶有不同的分值。Stella 通过控制箭塔选择目标，然后同时发射箭矢击中箭靶，从而获得分数以展示他的「射箭」技术。

你的任务是计算在给定的空地上，Stella 最多能获得多少分数。

限制条件

• 每个箭塔可以选择其指向方向上的任意一个箭靶，也可以选择不攻击。
• 每个箭塔的攻击范围内不会出现其他箭塔。
• 所有箭塔的攻击轨迹在地面上的投影不得在任意格子相交。

输入格式

第一行包含两个整数 $N$ 和 $M$。
接下来 $N$ 行，每行 $M$ 个字符，表示每个格子的状态：

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

输出格式

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

样例

输入

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

输出

10

数据范围与提示

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