1738. [HZOI 2014] 智哥的超时空传送

【题目描述】

    智哥在玩红色警戒这款游戏时学会了超时空传送，他利用这种神奇的科技时直接将物体传送到某个规定的位置，不论距离有多远。   

    智哥因为上课打红警（技术高超），被老师发现，（道高一尺，魔高一丈）。罚去操控一个采矿车，而且恼怒的老师是个贪财的家伙，他要求智哥采到最多的矿石，以满足他的贪欲，所以智哥要在操场旁的矿区（好屌的矿区！）开采。这个矿区是一个由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 

1 1 

1 * 

0 0

【样例输出】

3

【提示】

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

【来源】   

 hzoi2014