U472239 迷宫

游戏作者：@[Zhu_PingYuan](https://www.luogu.com.cn/user/1029108)，~~附上游戏~~，如果要玩的话存档要先创建一个 puzzle 文件夹才能存，不然存档会丢失。\ 众锁粥汁，zpy 的迷宫小游戏很~~不~~好玩，但美中不足的是，在计算迷宫获得分数时，由于~~最便宜~~ zpy 不会写 dfs 所以就算走了最优路径也不一定能拿到最高分，为了解决这个问题，zpy 想请你帮忙写一下 dfs 来计算最少的步数以及能获得的最大积分（包括迷宫内散落的积分）。\ 迷宫里有以下图标，分别表示不同的含义\ `#`：表示墙，除非有穿墙，否则不能走。\ `*`：起点和终点。起点在左上角，终点在右下角\ `$`：迷宫内散落的积分，每个可以获得 10 积分。\ `^`：钥匙，必须获得钥匙之后才能进入终点，但是需要花费 10 积分来获得钥匙，否则走到终点的步数认定为迷宫内所有可通行区域的个数之和（及 完整的 dfs 整个迷宫）。\ `_`：陷阱，踩到扣除 10 积分。\ `&`：传送门，每个地图有两个，到达此格时可以选择是否传送。 道具介绍：\ 穿墙：可以穿过一个`#`，穿墙这一步不计入步数，需要花费 20 积分。\ ~~翻倍卡片：可以使这一次积分翻倍，花费13积分,但是一局只能用一次。（应同学相应，本功能删除）~~

给定一个 $N \times M$ 由的迷宫，计算所用步数及积分 积分计算公式：$\frac{60}{x+55} \times n$，结果四舍五入 其中 $n = \frac{N+M}{2}$，$x$为步数\ 注意，若 $N,M \le 5$，则只生成起点，重点，墙和钥匙\ 道具商店内的所有道具均需要积分购买

第一行输入一个整数 $a$，表示初始积分\ 第二行两个整数 $N$ 和 $M$，表示迷宫的长和宽\ 接下来的 $N$ 行，给定迷宫的矩阵

输出共两行\ 第一行输出一个整数，表示迷宫的步数\ 第二行一个整数，表示这局迷宫的净收益（包括购买道具减去的积分及通过迷宫后获得的积分）\ 如果有多个答案，按照以下关键字输出：净收益更大，步数更少

样例 1 说明：不拿钥匙，共计15步，获得 4 分 对于 $100\%$ 的数据，$5 \le N,M \le 45$，$0 \le a \le 10^9$\ 这题有一个坑点，就是输入的 $N$ 和 $M$ 表示的长，宽是游玩区域，未把墙壁算上，所以实际上的迷宫范围是 $(N+2)\times(M+2)$