/* package codechef; // don't place package name! */
import java.util.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader sc = new BufferedReader(in);
int t = Integer.parseInt(sc.readLine());
for(int xyz = 0; xyz < t; xyz++)
{
Codechef ob = new Codechef();
ob.min = -1000000000;
String[] temp = sc.readLine().split(" ");
int n = Integer.parseInt(temp[0]);
ob.K = Integer.parseInt(temp[1]);
ob.grid = new char[n][];
ob.A = new int[n][n];
for(int i = 0; i < n; i++)
ob.grid[i] = sc.readLine().toCharArray();
for(int i = 0; i < n; i++)
{
temp = sc.readLine().split(" ");
for(int j = 0; j < n; j++)
ob.A[i][j] = Integer.parseInt(temp[j]);
}
ob.dp = new Integer[n][n][ob.K+1];
int ans = ob.solve(0, 0, ob.K);
if(ans < 0)
System.out.println(-1);
else
System.out.println(ans);
}
sc.close();
}
private int K, min;
private int[][] A;
private Integer[][][] dp;
private char[][] grid;
private int solve(int i, int j, int k)
{
if(k == -1 || i < 0 || j < 0 || i >= A.length || j >= A.length)
return min;
if(i == A.length-1 && j == A.length-1)
{
if(k == 0 && grid[i][j] == '#')
return min;
else
return A[i][j];
}
if(dp[i][j][k] != null)
return dp[i][j][k];
dp[i][j][k] = min;
if(grid[i][j] == '#' || k != K)
dp[i][j][k] = A[i][j] + Math.max(
solve(i+1, j, k-1),
solve(i, j+1, k-1));
if(grid[i][j] == '.')
{
if(k == K)
dp[i][j][k] = Math.max(dp[i][j][k], A[i][j] + Math.max(
solve(i+1, j, k),
solve(i, j+1, k)));
else
dp[i][j][k] = Math.max(dp[i][j][k], A[i][j] + Math.max(
solve(i+1, j, 0),
solve(i, j+1, 0)));
}
return dp[i][j][k];
}
}
Why is this giving TLE?