#include<bits/stdc++.h>
using namespace std;
const int INF = 1e7;
int n , s;
vector<vector<int>> secondsdiff;
vector<vector<bool>> grid;
vector<pair<int,int>> hives;
pair<int,int> home;
pair<int,int> honeypot;
vector<vector<int>> hivedist;
int dx[4] = {1 , -1 , 0 , 0};
int dy[4] = {0 , 0 , 1 , -1};
bool inside(int x, int y){
return x >= 0 && x < n && y >= 0 && y < n;
}
void bfs(queue<pair<int,int>> &q, vector<vector<int>> &v) {
while(!q.empty()) {
pair<int,int> cur = q.front();
q.pop();
for(int i = 0;i < 4; i++){
int tempx = cur.first + dx[i];
int tempy = cur.second + dy[i];
if(!inside(tempx, tempy) || !grid[tempx][tempy] || v[tempx][tempy] != INF) {
continue;
}
q.push(pair(tempx, tempy));
v[tempx][tempy] = v[cur.first][cur.second] + 1;
}
}
}
bool valid( int mid){
vector<vector<int>> mechodist(n , vector<int> (n, INF));
mechodist[honeypot.first][honeypot.second] = mid * s;
queue<pair<int,int>> q;
q.push(honeypot);
while(!q.empty()) {
pair<int,int> cur = q.front();
q.pop();
if((mechodist[cur.first][cur.second] - 1) / s >= hivedist[cur.first][cur.second] ) {
continue;
}
if(cur == home){
return true;
}
for(int i = 0; i < 4 ;i++){
int curx = cur.first + dx[i];
int cury = cur.second + dy[i];
if(!inside(curx, cury) || !grid[curx][cury] || mechodist[curx][cury] != INF){
continue;
}
mechodist[curx][cury] = mechodist[cur.first][cur.second] + 1;
q.push(pair(curx, cury));
}
}
return false;
}
int main (){
cin >> n >> s;
grid.resize(n , vector<bool>(n));
hivedist.resize(n, vector<int>(n, INF));
for(int i = 0;i < n ;i++){
for(int j = 0;j < n;j++){
char c;
cin >> c;
if(c == 'T') {
grid[i][j] = false;
}
else if(c == 'G'){
grid[i][j] = true;
}
else if(c == 'M'){
grid[i][j] = true;
honeypot = pair(i , j);
}
else if(c == 'D') {
grid[i][j] = false;
home = pair(i , j);
}
else {
grid[i][j] = true;
hives.push_back(pair(i, j));
}
}
}
queue<pair<int,int>> q;
for(auto &x : hives){
q.push(x);
hivedist[x.first][x.second] = 0;
}
//multisource bfs for bees
bfs(q, hivedist);
//now mecho can enter his home, but he can't enter the hives
for(auto &x : hives){
grid[x.first][x.second] = false;
}
grid[home.first][home.second] = true;
int l = -1, r = 1e6 + 1;
while(l < r - 1){
int mid = (l + r) / 2;
if(valid(mid)){
l = mid;
}
else {
r = mid;
}
}
int ans = l;
cout << ans << endl;
}
