You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你一定知道红色警戒这款游戏吧，在这个游戏里有一种神奇的科技被称作超时空传送，当一个物体使用这种神奇的科技时，它会直接被传送到某个规定的位置，不论距离有多远。 现在这里有一处矿区，而你正操控着一个采矿车。你的任务是在这个矿区获取最多的矿石。这个矿区是一个由n*m个小格子组成的矩形区域，其中一些格子有矿石，而另一些没有。矿石只能被采集一遍，而不会重新产生。 矿车的初始位置为该矩形地区的西北角。它只能向东或向南的临近的格子移动，而不能向北或向西移动。一些格子有传送门而使矿车可以通过超时空传送到达某个特定的格子。 现在，因为你是这个矿车的指挥，所以你要来决定是否使用传送门（可以选择留在原地）。而这种传送门是永远不会消失的，当你到达有这种传送门的格子时，就可以立刻使用它。

输入格式

输入的第一行为一个整数T(1<=T<=5)，表示数据的组数。
对于每一组数据，第一行是两个由空格隔开的整数N和M(2<=N,M<=40)。
接下来的N行每行将是一个包含M个字符的字符串。
每一个字符可以是一个整数X(0<=X<=9)或一个“*”或一个“#”。
如果是一个整数X表示这个格子有X单位的矿石，当你的矿车经过这里时可以把它们全部采集走。
如果是“*”则表示在这个格子有一个传送门。
如果是“#”则表示在这个格子里是有障碍物而不能到达的。
矿车的起始位置一定没有障碍物。
就上面的地图显示的，地图中一共有K个“*”。接下来的K行描述每个传送门传送的目的地，按照传送门的位置从北到南，从西到东的顺序给出（即逐行给出）。（传送门的目的地的横纵坐标是从0到N-1,0到M-1的）

输出格式

对于每一组数据，你应该输出你最多能够获得多少单位的矿石。

1
2 2
11
1*
0 0

3

提示

你的终点是任意的，你不能走到地图外，传送门是不会把你传送到地图外的。