题目描述

小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 $N×N$ 个格子组成的 2D 迷宫。

小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。

每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。

迷宫中有些格子小明可以经过，我们用 '.' 表示。

有些格子是墙壁，小明不能经过，我们用 '#' 表示。

此外，有些格子上有陷阱，我们用 'X' 表示。除非小明处于无敌状态，否则不能经过。

有些格子上有无敌道具，我们用 '%' 表示。

当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 $K$ 步。

之后如果再次到达该格子不会获得无敌状态了。

处于无敌状态时，可以经过有陷阱的格子，但是不会拆除/毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。

给定迷宫，请你计算小明最少经过几步可以离开迷宫?

输入描述

第一行包含两个整数 $N,K (1≤N≤1000,1≤K≤10)$ 。

以下 $N$ 行包含一个 $N×N$ 的矩阵。

矩阵保证左上角和右下角是 '.'。

一个整数表示答案。如果小明不能离开迷宫，输出 -1。

5 3
...XX
##%#.
...#.
.###.
.....