#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
int dx[4] = {0, -1, 1, 0};
int dy[4] = {1, 0, 0, -1};
long long n, s;
int si, sj, fi, fj;
char grid[802][802];
long long reach[802][802], d[802][802];
bool vis[802][802];
void print()
{
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) cout<<reach[i][j]<<" ";
cout<<endl;
}
}
void INIT()
{
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
vis[i][j] = false;
d[i][j] = INT_MAX;
}
}
}
void flood()
{
queue<ii> q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) if(grid[i][j] == 'H'){
vis[i][j] = true;
q.push(ii(i, j));
}
}
while(!q.empty()){
int ui = q.front().first, uj = q.front().second;
q.pop();
for(int i = 0; i < 4; i++){
int vi = ui + dx[i], vj = uj + dy[i];
if(vi >= 1 && vi <= n && vj >= 1 && vj <= n){
if(!vis[vi][vj] && grid[vi][vj] != 'T' && grid[vi][vj] != 'D'){
vis[vi][vj] = true;
reach[vi][vj] = reach[ui][uj] + s;
q.push(ii(vi, vj));
}
}
}
}
}
bool check(long long k)
{
INIT();
d[si][sj] = k * s;
if(d[si][sj] >= reach[si][sj]) return false;
reach[fi][fj] = INT_MAX;
vis[si][sj] = true;
queue<ii> q;
q.push(ii(si, sj));
while(!q.empty()){
int ui = q.front().first, uj = q.front().second;
q.pop();
if((ui >= fi - 1 && ui <= fi + 1 && uj == fj)||(ui == fi && uj <= fj + 1 && uj >= fj - 1)){
return true;
}
for(int i = 0; i < 4; i++){
int vi = ui + dx[i], vj = uj + dy[i];
if(vi < 1 || vi > n || vj < 1 || vj > n) continue;
if(reach[vi][vj] > d[ui][uj] + 1 && !vis[vi][vj] && grid[vi][vj] != 'T'){
vis[vi][vj] = true;
d[vi][vj] = d[ui][uj] + 1;
q.push(ii(vi, vj));
}
}
}
return false;
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
cin>>n>>s;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin>>grid[i][j];
if(grid[i][j] == 'M'){
si = i;
sj = j;
}
if(grid[i][j] == 'D'){
fi = i;
fj = j;
}
}
}
flood();
//print();
long long lo = 0, hi = 1000000000;
while(lo < hi){
long long mid = lo + (hi - lo + 1) / 2;
if(check(mid)){
lo = mid;
}
else{
hi = mid - 1;
}
}
if(!check(lo)) cout<<-1;
else cout<<lo;
return 0;
}
