30

#include<bits/stdc++.h>
using namespace std;
const int N=1002;
struct node{
	int x,y,w,c;
};
int n,k,xj[6]={0,0,-1,0,1},yj[6]={0,1,0,-1,0};
string s[N];
int vis[N][N];
int main() {
	ios::sync_with_stdio(0);
	memset(vis,-1,sizeof(vis));
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		cin>>s[i];
		s[i]=" "+s[i];
	}
	queue<node>q;
	q.push((node){1,1,0,0});
	vis[1][1]=0;
	while(!q.empty()){
		node now=q.front();
		int x=now.x,y=now.y,w=now.w,c=now.c;
		if(x==n&&y==n){
			cout<<c;
			return 0;
		}
		q.pop();
	//	cout<<"("<<x<<","<<y<<")"<<w<<"$"<<"\n";
		
		for(int i=1;i<=4;i++){
			int xx=x+xj[i],yy=y+yj[i];
			if(xx<1||xx>n||yy<1||yy>n||(s[xx][yy]=='X'&&w==0)|| s[xx][yy]=='#')continue;
			int wd=max(w-1,0);
			if(s[xx][yy]=='%'){
				wd=k;
			}
			if(wd>vis[xx][yy]){
				q.push((node){xx,yy,wd,c+1});
				vis[xx][yy]=wd;	
			}
		}
	}
	cout<<-1;
}
/*

*/