#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define MOD (ll) (1e9+7)
#define pii pair<int,int>
#define ff first
#define ss second
int n,s;
pii start,finish;
string board[801];
vector<vector<int>> beedist(801, vector<int>(801, -1));
queue<pii> bees;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool inBounds(pii asdf) {
int x=asdf.ff; int y=asdf.ss;
return (x>=0 && x<n && y>=0 && y<n && board[x][y]!='T');
}
void beeDist() {
while(!bees.empty()) {
auto curr = bees.front(); bees.pop();
for(int i=0; i<4; i++) {
pii next = {curr.first+dx[i], curr.second+dy[i]};
if(inBounds(next) && beedist[next.ff][next.ss] == -1 && board[next.ff][next.ss]!='D') {
beedist[next.ff][next.ss] = beedist[curr.ff][curr.ss] + s;
bees.push(next);
}
}
}
}
bool test(int delay) {
vector<vector<int>> dist(801, vector<int>(801, -1));
if(delay*s>=beedist[start.ff][start.ss]) {
return false;
}
queue<pii> q; q.push(start);
dist[start.ff][start.ss] = delay*s;
while(!q.empty()) {
auto curr = q.front(); q.pop();
if(curr == finish) {
return true;
}
for(int i=0; i<4; i++) {
pii next = {curr.ff+dx[i], curr.ss+dy[i]};
if(inBounds(next)&&((dist[curr.ff][curr.ss]+1)<beedist[next.ff][next.ss])&&dist[next.ff][next.ss]==-1) {
dist[next.ff][next.ss] = dist[curr.ff][curr.ss]+1;
q.push(next);
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin>>n>>s;
for(int i=0; i<n; i++) {
cin>>board[i];
for(int j=0; j<n; j++) {
if(board[i][j] == 'M') {
start.ff = i;
start.ss = j;
} else if (board[i][j] == 'D') {
finish.ff = i;
finish.ss = j;
} else if (board[i][j] == 'H') {
beedist[i][j] = 0;
bees.push({i,j});
}
}
}
beeDist();
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) {
// cout<<beedist[i][j]<<' ';
// }
// cout<<endl;
// }
// cout<<test(0)<<endl;
// cout<<test(1)<<endl;
// cout<<test(2)<<endl;
// cout<<test(3)<<endl;
beedist[finish.ff][finish.ss] = n*n*s;
//binsearch :D
int lo = -1; int hi = 2*n*n;
while(hi-lo>1) {
int mid = (lo+hi)>>1;
if(test(mid)) {
lo = mid;
} else {
hi = mid;
}
}
cout<<lo<<endl;
return 0;
}
