Treasure Hunt Adventure

A participant is given an n \times n grid representing a treasure map. Each cell of the grid either contains a treasure chest (denoted by X) or is empty (denoted by .). Starting from the top-left cell, the participant is allowed to take exactly k steps. In each step, the participant may move to an adjacent cell (up, down, left, or right), provided that the cell has not been visited before in the current path.

A treasure is collected if the participant steps onto a cell containing an X. Note that if the starting cell contains a treasure, it is counted as well. The objective is to determine the maximum number of treasures that can be collected in exactly k moves.

The moves must be exactly of length k and the path should not revisit any cell.

The problem can be modeled with the following constraints using recursion and backtracking. In each recursive step, if the participant has no remaining moves, the recursion terminates. Otherwise, the participant attempts all four possible moves while keeping track of cells already visited.

Formally, let \(f(x,y,s)\) be the maximum number of treasures that can be collected from cell \((x,y)\) with exactly \(s\) steps remaining. Then, for each valid move to a neighbor \((x+dx,y+dy)\) that has not been visited, we update: \[ f(x,y,s) = \max_{(dx,dy)} \big\{ \mathbf{1}_{\{grid[x+dx][y+dy]=X\}} + f(x+dx,y+dy,s-1) \big\}. \]

inputFormat

The first line contains two integers, n and k, where n is the dimension of the grid and k is the exact number of moves permitted.

The following n lines each contain a string of n characters representing the grid. Each character is either X (treasure) or . (empty cell). There are no spaces between characters.

outputFormat

Output a single integer representing the maximum number of treasure chests that can be collected with exactly k moves.

## sample

3 2
.X.
..X
X.X

1

</p>