#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i=a; i<=b; i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define f first
#define s second
#define nl '\n'
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef pair<int, int> pii;
#define nl '\n'
const int N=800;
int n, s;
string grid[N];
int dist[N][N];
int dist2[N][N];
bool block[N][N];
int dx[]={0, 0, 1, -1};
int dy[]={1, -1, 0, 0};
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> s;
for(int i=0; i<n; i++){
cin >> grid[i];
}
auto check=[&](int t)->bool{
queue<pair<int,int>> q;
rep(i,0,n-1) rep(j,0,n-1){
dist[i][j]=-1;
block[i][j]=0;
if(grid[i][j]=='H'){
dist[i][j]=0;
q.push({i,j});
}
}
while(!q.empty()){
pair<int,int> p=q.front();
int x=p.first, y=p.second;
if(dist[x][y]>t) break;
block[x][y]=1;
// cout << "block " << x << " " << y << "\n";
q.pop();
for(int k=0; k<4; k++){
int nx=x+dx[k];
int ny=y+dy[k];
if(nx<0 || nx==n || ny<0 || ny==n || grid[nx][ny]=='T' || grid[nx][ny]=='D') continue;
if(dist[nx][ny]==-1){
dist[nx][ny]=dist[x][y]+1;
q.push({nx,ny});
}
}
}
int it=0;
queue<pair<int,int>> q2;
rep(i,0,n-1) rep(j,0,n-1){
if(grid[i][j]=='M') q2.push({i,j}), dist2[i][j]=0;
else dist2[i][j]=-1;
}
while(true){
it++;
bool move=0;
while(!q2.empty()){
pair<int,int> p=q2.front();
int x=p.first, y=p.second;
if(dist2[x][y]>it*s) break;
q2.pop();
if(block[x][y]) continue;
move=1;
if(grid[x][y]=='D') return 1;
for(int k=0; k<4; k++){
int nx=x+dx[k];
int ny=y+dy[k];
if(nx<0 || nx==n || ny<0 || ny==n || block[nx][ny] || grid[nx][ny]=='T' || grid[nx][ny]=='H' || dist2[nx][ny]!=-1) continue;
dist2[nx][ny]=dist2[x][y]+1;
q2.push({nx,ny});
}
}
if(!move) break;
while(!q.empty()){
pair<int,int> p=q.front();
int x=p.first, y=p.second;
if(dist[x][y]>t+it) break;
block[x][y]=1;
q.pop();
for(int k=0; k<4; k++){
int nx=x+dx[k];
int ny=y+dy[k];
if(nx<0 || nx==n || ny<0 || ny==n || grid[nx][ny]=='T' || grid[nx][ny]=='D') continue;
if(dist[nx][ny]==-1){
dist[nx][ny]=dist[x][y]+1;
q.push({nx,ny});
}
}
}
}
return 0;
};
int x=0;
for(int i=20; i>=0; i--){
if(check(x+(1<<i))) x+=(1<<i);
}
cout << (check(x)?x:-1);
// rep(i,0,10) cout << check(i) << "\n";
}
