#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD (1LL<<63)
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ld long double
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
#define Max(a) (*max_element(ALL(a)))
#define Min(a) (*min_element(ALL(a)))
using namespace std;
vvi vis(2222,vi(2222,llINF));
ll vx[4] = {1,0,-1,0};
ll vy[4] = {0,1,0,-1};
ll h,w;
vi ch(33);
bool check(ll x,ll y){
  return x>=0 && x<h && y>=0 && y<w;
}
int main(){
  cin>>h>>w;
  string s[h];
  vector<vector<pair<ll,ll>>>E(33);
  queue<pair<ll,ll>>que;
  for(int i=0;i<h;i++){
    cin>>s[i];
    for(int j=0;j<w;j++){
      if(s[i][j] == 'S'){
	que.push(mp(i,j));
	vis[i][j] = 0;
      }
      if('a' <= s[i][j] && s[i][j] <= 'z'){
	E[s[i][j]-'a'].pb(mp(i,j));
      }
    }
  }

  while(!que.empty()){
    ll x,y;
    tie(x,y) = que.front();
    que.pop();
    //cout<<x<<" "<<y<<" "<<vis[x][y]<<endl;
    if(s[x][y] == 'G'){
      cout<<vis[x][y]<<endl;
      return 0;
    }
    if('a' <= s[x][y] && s[x][y] <= 'z'){
      if(ch[s[x][y]-'a']){}
      else{
	ch[s[x][y]-'a'] = 1;
	for(auto e:E[s[x][y]-'a']){
	  //cout<<e.F<<" "<<e.S<<endl;
	  if(vis[e.F][e.S] > vis[x][y]+1){
	    vis[e.F][e.S] = vis[x][y] + 1;
	    que.push(mp(e.F,e.S));
	  }
	}
      }
    }
    for(int i=0;i<4;i++){
      ll nx = x+vx[i],ny = y+vy[i];
      if(check(nx,ny) && s[nx][ny] != '#'&& vis[nx][ny] > vis[x][y]+1){
	//cout<<nx<<" "<<ny<<endl;
	vis[nx][ny] = vis[x][y]+1;
	que.push(mp(nx,ny));
      }
    }
  }
  cout<<-1<<endl;
  return 0;
}


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define spu  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
// ~ ~ ~ ~ minmedian ~ ~ ~ ~ 
// ~ ~ ~ ~    median ~ ~ ~ ~ 
//dp+二分
//dp策略：遍历每一个格子，以当前格子为右下角的方阵有多少个格子小于等于给定值 
//二分策略： 对于mid  如果存在一种sqare cnt>= (k*k+1)/2 在左面找，else 在右面找
const int N=810;
int k,n;
int g[N][N];
int dp[N][N];
bool check(int mid)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=g[i][j]<=mid;
			
			dp[i][j]+=dp[i-1][j];
			dp[i][j]+=dp[i][j-1];
			dp[i][j]-=dp[i-1][j-1];
		}
	}
	for(int i=k;i<=n;i++) 
	{
		for(int j=k;j<=n;j++)
		{
			int cnt=dp[i][j];
			cnt-=dp[i][j-k];
			cnt-=dp[i-k][j];
			cnt+=dp[i-k][j-k];
			if(cnt>=(k*k+1)/2) return true;
		}
	}
	return false;
}
int main()
{
	spu;
	cin>>n>>k;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>g[i][j];
	int l=-1,r=1e9;
	while(r-l>1)
	{
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid;
	}
	cout<<r<<endl;

	
}