#include<bits/stdc++.h>
using namespace std;
int n, k, vis[1005][1005];
const pair<int, int> dir[]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
deque<tuple<int, int, int, int>> dq;
vector<string> v(1);
char getch(){
	char c;
	while(!isalpha(c = getchar()) and !ispunct(c));
	return c;
}signed main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i){
		string s(1, ' ');
		for(int j = 1; j <= n; ++j)
			s.push_back(getch());
		v.push_back(s);
	}dq.push_back({1, 1, 0, 0});
	memset(vis, -1, sizeof(vis));
	while(dq.size()){
		tuple<int, int, int, int> t = dq[0];
		dq.pop_front();
		for(pair<int, int> p: dir){
			int x = get<0>(t) + get<0>(p), y = get<1>(t) + get<1>(p);
			int st = get<2>(t) + 1, mag = max(0, get<3>(t) - 1);
			if(x == n and y == n){
				printf("%d", st);
				return 0;
			}if(x < 1 or x > n or y < 1 or y > n) continue;
			if(v[x][y] == '%') mag = k;
			if(v[x][y] == '#' or v[x][y] == 'X' and !mag or vis[x][y] >= mag) continue;
			vis[x][y] = mag;
			dq.push_back({x, y, st, mag});
		}
	}printf("-1");
	return 0;
}