Description

Xiaoming is playing a maze game. In the game, he needs to control his character to leave a 2D maze made up of an $N \times N$ grid.

Xiaoming starts at the upper-left corner. He needs to reach the lower-right cell to leave the maze.

At each step, he can move to one of the four adjacent cells (up, down, left, right), provided that the target cell is passable.

In the maze, some cells are passable, denoted by ..

Some cells are walls and cannot be passed, denoted by #.

In addition, some cells contain traps, denoted by X. Unless Xiaoming is in an invincible state, he cannot pass through them.

Some cells contain an invincibility item, denoted by %.

When Xiaoming reaches such a cell for the first time, he automatically gains an invincible state, which lasts for $K$ steps.

After that, if he reaches the same cell again, he will not gain the invincible state anymore.

While in the invincible state, he can pass through cells with traps, but he will not remove / destroy the traps. That is, the traps will still block characters that are not in the invincible state.

Given the maze, compute the minimum number of steps Xiaoming needs to leave the maze.

Input Format

The first line contains two integers $N$ and $K$. $(1 \le N \le 1000，1 \le K \le 10)$.

The next $N$ lines contain an $N \times N$ matrix.

The matrix guarantees that the upper-left corner and the lower-right corner are ..

Output Format

Output one integer representing the answer. If Xiaoming cannot leave the maze, output $-1$.

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

10

5 1
...XX
##%#.
...#.
.###.
.....

12

Hint

Time limit: 3 seconds, 256M. Lanqiao Cup 2018, 9th National Finals.

Translated by ChatGPT 5