U241812 传送

无

【题目描述】： 现在这里有一处矿区，而你正操控着一个采矿车。你的任务是在这个矿区获取最多的矿石。这个矿区是一个由n×m个小格子组成的矩形区域，其中一些格子有矿石，而另一些没有。矿石只能被采集一遍，而不会重新产生。 矿车的初始位置为该矩形地区的西北角。它只能向东或向南的临近的格子移动，而不能向北或向西移动。一些格子有传送门而使矿车可以通过超时空传送到达某个特定的格子。 现在，因为你是这个矿车的指挥，所以你要来决定是否使用传送门（可以选择留在原地）。而这种传送门是永远不会消失的，当你到达有这种传送门的格子时，就可以立刻使用它。

【输入描述】： 输入的第一行为一个整数T(1

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

【提示】： 你的终点是任意的，你不能走到地图外，传送门是不会把你传送到地图外的。 【时间限制、数据范围及描述】： 时间：500ms 空间：256M 10%的数据： N×M