for y in range(self.height):
            for x in range(self.width):
                s = 0
                for dy in range(-1, 2):
                    for dx in range(-1, 2):
                        if x + dx < 0 or x + dx >= self.width or y + dy < 0 or y + dy >= self.height:
                            continue
                        s += self.board[y + dy][x + dx]
                s -= self.board[y][x]

def solve(grid, k):
   visited = [[False] * len(grid[0]) for _ in range(len(grid))]
   reach, res = dfs(0, 0, k, grid, visited)
   return res if reach else 0

def dfs(i, j, k, grid, visited):
   if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or not k or visited[i][j] or not grid[i][j]: return False, 0
   if i == len(grid) - 1 and j == len(grid[0]) - 1: return True, grid[i][j] - 1
   max_reach, max_sum = False, 0
   visited[i][j] = True
   for i, j in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
       reach, sum = dfs(i, j, k-1, grid, visited)
       if reach: max_reach, max_sum = True, max(max_sum, sum)
   visited[i][j] = False
   return max_reach, grid[i][j] - 1 + max_sum if max_reach else False, 0