U611926 游戏

有一款在 $n\times m$ 的地图上进行的游戏，地图上有一些电磁炮和一些敌方建筑，消灭等级为 $x$ 的建筑可以得到 $x$ 的经验。你的目标是得到尽可能多的总经验。 电磁炮有上、下、左、右四种发射方向，每个电磁炮的方向都是固定的。你可以设定每个电磁炮的射程 $d$，这样电磁炮就会瞄准发射方向上距离恰为d的建筑并消灭它。比如一个向上的电磁炮在 $(3,2)$，如果射程为 $2$，那么 $(1,2)$ 的敌人会被消灭。当然你也可以选择不用其中某些电磁炮。 为了保证安全，地图保证每个电磁炮都无法攻击到其他的电磁炮。另外，你需要保证任何两个电磁炮的发射路径（指从电磁炮到它瞄准的目标点的直线路径上的格子，包括端点）不能相交。现在请你求出你能获得的最多经验。

第一行给出数据组数 $T$。每组数据的格式如下： 第一行给出两个正整数 $n,m$，表示的地图大小为 $n$ 行 $m$ 列。 接下来是一个 $n$ 行 $m$ 列的字符矩阵表示地图，$1\sim 9$ 表示等级$1\sim 9$ 的建筑，A V < > 表示发射方向分别为上、下、左、右的电磁炮，其它空地用 . 表示。

输出共 $T$ 行，表示每一个数据的最多经验。

对于 $10\%$ 的数据，$n,m\le 3$. 对于 $30\%$ 的数据，$n,m\le 6$. 对于 $100\%$ 的数据，$T\le 10,n,m\le 50$.