#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
vector<vector<char>> grid;
vector<vector<ll>> minReachBees;
vector<vector<ll>> mr;
vector<vector<bool>> vis;
queue<pair<ll, ll>> q;
ll n, s;
ll isOk1(ll y, ll x, ll tm){
if(y>=n||x>=n||y<0||x<0) return 0;
if(minReachBees[y][x] <= tm) return 0 ;
if(grid[y][x] != 'G' && grid[y][x] != 'H') return 0;
minReachBees[y][x] = tm;
return 1;
}
void upd(ll y, ll x){
ll tm = minReachBees[y][x];
if(isOk1(y+1, x, tm+1)) q.push({y+1, x});
if(isOk1(y-1, x, tm+1)) q.push({y-1, x});
if(isOk1(y, x+1, tm+1)) q.push({y, x+1});
if(isOk1(y, x-1, tm+1)) q.push({y, x-1});
while(!q.empty()){
auto tmp = q.front();
q.pop();
upd(tmp.first, tmp.second);
}
}
ll isOk2(ll y, ll x, ll tm){
if(y>=n||x>=n||y<0||x<0) return 0;
if(mr[y][x] <= tm) return 0 ;
if(grid[y][x] == 'T') return 0;
if(vis[y][x] == 1) return 0;
if(tm/s >= minReachBees[y][x]) return 0;
mr[y][x] = tm;
return 1;
}
void check(ll y, ll x){
vis[x][y] = 1;
ll tm = mr[y][x];
if(isOk2(y+1, x, tm+1)) q.push({y+1, x});
if(isOk2(y-1, x, tm+1)) q.push({y-1, x});
if(isOk2(y, x+1, tm+1)) q.push({y, x+1});
if(isOk2(y, x-1, tm+1)) q.push({y, x-1});
while(!q.empty()){
auto tmp = q.front();
q.pop();
check(tmp.first, tmp.second);
}
}
int main(void){
// freopen("input.txt", "r", stdin);
cin>>n>>s;
grid.assign(n, vector<char>(n, 0));
minReachBees.assign(n, vector<ll>(n, 100000000000));
for(ll i = 0; i<n; i++){
string str; cin>>str;
for(ll j = 0; j<n; j++){
grid[i][j] = str[j];
}
}
pair<ll, ll> m;
pair<ll, ll> h;
for(ll i = 0; i<n; i++){
for(ll j = 0; j<n; j++){
if(grid[i][j] == 'H'){
minReachBees[i][j] = 0;
upd(i, j);
}
if(grid[i][j] == 'M'){
m = {i, j};
}
if(grid[i][j] == 'D'){
h = {i, j};
}
}
}
mr.assign(n, vector<ll>(n, 100000000000));
vis.assign(n, vector<bool>(n, 0));
mr[m.first][m.second] = 0;
check(m.first, m.second);
if(mr[h.first][h.second] == 100000000000){
cout<<-1<<endl;
return 0;
}
ll l = 0, r = 100000000000;
while(l<r){
ll mid = (l+r+1)/2;
mr.assign(n, vector<ll>(n, 100000000000));
vis.assign(n, vector<bool>(n, 0));
mr[m.first][m.second] = mid*s;
check(m.first, m.second);
if(mr[h.first][h.second] != 100000000000) l = mid;
else r = mid-1;
}
cout<<l<<endl;
return 0;
}
