​【​​​题目描述​】

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

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

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

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

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

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

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

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

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

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

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

​【​​​输入格式​】

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

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

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

​【​​​输出格式​】

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

​【​​输入​样例1】

5 3

...XX

##%#.

...#.

.###.

.....

​【​​输出​样例1】

10

​【​​输入​样例2】

5 1

...XX

##%#.

...#.

.###.

.....

​【​​输出​样例2】

12