### 问题描述 小明正在玩一款名为农夫与蛇的游戏，在一个 $n \times n$ 的蛇洞中，农夫要从左上角 $(1,1)$ 的位置开始逃离蛇洞，每次可以向四个方向移动(前后左右)。 每方格可能会有捕蛇道具(如果有捕蛇道具，可以在遇到蛇的时候使用用 ```%``` 表示捕蛇道具)，捕蛇道具是消耗品，使用则数量减 $1$ 。也可能是蛇( ```&``` 表示蛇)，如果遇到蛇，在没有道具的保护下，会扣 $1$ 血量值，还有一种就是遇到死胡同( ```#``` 表示不可走)，```*``` 表示空地(无任何限制)。 农夫一开始血量值为 $k$，出口位置在右下角 $(n,n)$ ，农夫要逃离蛇洞，请计算他逃离蛇洞的最少步数(到出口后农夫血量值为正整数才算逃离)，如果不能逃离则输出 $null$ 。 ### 输入格式 第一行输入两个整数 $n,k$ ( $2 \leq n \leq 1000$ , $1 \leq n \leq 100$ )。 第 $2$ 到 $n + 1$ 每行包含 $n$ 个字符，表示地图上该位置的信息。 ### 输出格式 输出仅一行，如果能逃离，则输出农夫逃离最少步数，否则输出 $null$。 ### 样例输入 ``` 5 3 ***%# ##%## &**#& **##& &**** ``` ### 样例输出 ``` 10 ```