#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] == 'T' || grid[y][x] == 'D') return 0;
minReachBees[y][x] = tm;
return 1;
}
void upd(){
while(!q.empty()){
int x = q.front().second;
int y = q.front().first;
q.pop();
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});
}
}
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 >= minReachBees[y][x]*s) return 0;
mr[y][x] = tm;
return 1;
}
void check(){
while(!q.empty()){
int x = q.front().second;
int y = q.front().first;
q.pop();
vis[y][x] = 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});
}
}
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;
q.push({i, j});
upd();
}
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;
q.push({m.first, m.second});
check();
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;
q.push({m.first, m.second});
check();
int cor = 0;
if(minReachBees[m.first][m.second] <= mid){
r = mid-1;
//continue;
}
// if(h.first<n-1 && mr[h.first+1][h.second] != 100000000000) cor = 1;
// if(h.first>0 && mr[h.first-1][h.second] != 100000000000) cor = 1;
// if(h.second>0 && mr[h.first][h.second-1] != 100000000000) cor = 1;
// if(h.second<n-1 && mr[h.first][h.second+1] != 100000000000) cor = 1;
else if(mr[h.first][h.second] != 100000000000 || cor) l = mid;
else r = mid-1;
}
cout<<l<<endl;
return 0;
}
