#include<bits/stdc++.h>
#define int long long
using namespace std;
string s[1005];
int ar[1005][1005];
int vis[1005][1005];
int bear[1005][1005],bee[1005][1005];
int val[1005][1005];
pair<int,int>dir[4]={
{0,1},{1,0},{0,-1},{-1,0}
};
int inf=1e9;
int n,k;
pair<int,int>st,en;
int check(int m){
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)vis[i][j]=0,bear[i][j]=inf;
queue<pair<int,int>>q;
q.push(st);
vis[st.first][st.second]=1;
bear[st.first][st.second]=0;
int cur=m;
//cerr<<"workk\n";
while(!q.empty()){
auto x=q.front();
q.pop();
//cerr<<"go:"<<x.first<<" "<<x.second<<" "<<bear[x.first][x.second]<<"\n";
for(int i=0;i<4;i++){
int xx=x.first+dir[i].first;
int yy=x.second+dir[i].second;
int tme=bear[x.first][x.second];
if(xx<1||xx>n||yy<1||yy>n||vis[xx][yy]||ar[xx][yy]==0||m+(tme)/k>=bee[x.first][x.second])continue;
bear[xx][yy]=bear[x.first][x.second]+1;
q.push({xx,yy});
vis[xx][yy]=1;
}
}
return vis[en.first][en.second];
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++)cin>>s[i];
vector<pair<int,int>>v;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
bear[i][j]=bee[i][j]=inf;
if(s[i-1][j-1]=='T');
else if(s[i-1][j-1]=='G')ar[i][j]=1;
else if(s[i-1][j-1]=='M')st={i,j},ar[i][j]=1;
else if(s[i-1][j-1]=='D')en={i,j},ar[i][j]=2;
else v.push_back({i,j});
}
}
queue<pair<int,int>>q;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)vis[i][j]=0;
for(auto x:v){
q.push(x);
vis[x.first][x.second]=1;
bee[x.first][x.second]=0;
}
while(!q.empty()){
auto x=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx=x.first+dir[i].first;
int yy=x.second+dir[i].second;
if(xx<1||xx>n||yy<1||yy>n||vis[xx][yy]||ar[xx][yy]!=1)continue;
bee[xx][yy]=bee[x.first][x.second]+1;
q.push({xx,yy});
vis[xx][yy]=1;
}
}
//cerr<<"work\n";
int l=0,r=1e9,ans=-1;
while(l<=r){
int m=(l+r)/2;
//cerr<<"m:"<<m<<"\n";
if(check(m)){
ans=m;
l=m+1;
}else{
r=m-1;
}
}
cout<<ans;
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)cerr<<bear[i][j]<<"\t";
cerr<<"\n";
}
cerr<<"\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)cerr<<bee[i][j]<<"\t";
cerr<<"\n";
}
cerr<<"\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)cerr<<val[i][j]<<"\t";
cerr<<"\n";
}
cerr<<"\n";*/
}
