#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 801,INF=1e12;
int n , o, srcx, srcy, destx, desty, ar[N][N];
int dx[4]={0,-1,1,0};
int dy[4]={-1,0,0,1};
struct node{
int x, y, dist;
};
bool valid1(int x, int y){
if(x>=0 && x<n && y>=0 && y<n && (x!=srcx || y!=srcy) && (x!=destx || y!=desty)) return true;
return false;
}
bool valid(int x, int y){
if(x>=0 && x<n && y>=0 && y<n) return true;
return false;
}
bool check(int mins)
{
vector<pair<int,int>>hives;
int arr[n][n],arr2[n][n];
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ; j ++)
{
arr[i][j]=ar[i][j]; arr2[i][j]=1;
if(arr[i][j]==1) hives.push_back({i,j});
}
queue<pair<int,int>>q;
int vis[n][n];
memset(vis,0,sizeof vis);
for(auto e : hives){
q.push({e.first,e.second});
vis[e.first][e.second]=1;
}
while(!q.empty())
{
int curx=q.front().first;
int cury=q.front().second;
q.pop();
for(int i = 0 ; i < 4; i ++)
{
int gox = curx+dx[i], goy = cury+dy[i];
if(valid(gox,goy) && !vis[gox][goy] && !arr[gox][goy]){
vis[gox][goy]=1;
arr[gox][goy]=arr[curx][cury]+1;
q.push({gox,goy});
}
}
}
queue<pair<pair<int,int>,int>>qq;
memset(vis,0,sizeof vis);
qq.push({{srcx,srcy},0});
vis[srcx][srcy]=1;
if(arr[srcx][srcy]<=mins) return false;
arr[srcx][srcy]=1;
while(!qq.empty()){
int curx=qq.front().first.first;
int cury=qq.front().first.second;
int c = qq.front().second;
if(curx==destx&&cury==desty) return true;
qq.pop();
for(int i = 0 ; i < 4; i ++)
{
int gox = curx+dx[i], goy = cury+dy[i];
if(valid(gox,goy) && !vis[gox][goy] && arr[gox][goy]!=-1){
if(mins+arr2[curx][cury]+(c%o==0&&c>0) < arr[gox][goy]){
vis[gox][goy]=1;
if(c%o!=0||!c)
arr2[gox][goy]=arr2[curx][cury];
else
arr2[gox][goy]=arr2[curx][cury]+1;
qq.push({{gox,goy},c+1});
}
}
}
}
return false;
}
int32_t main()
{
//freopen("abc.in", "r", stdin);
cin >> n >> o;
int id[n][n];
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j ++){
char x; cin >> x;
ar[i][j] = (x=='H'?1:((x=='G'||x=='D'||x=='M')?0:-1));
if(x=='M') srcx=i, srcy=j;
if(x=='D') destx=i, desty=j;
}
}
int l = 0 , r = n*n;
int ans=-1;
while(l <= r)
{
int mid = (l+r)/2;
if(check(mid))
{
l = mid+1;
ans=mid;
}
else
{
r = mid-1;
}
}
cout<<ans<<endl;
}
