#include <bits/stdc++.h>
using namespace std;
int n, s;
char ma[802][802];
int enj[802][802];
int pa[802][802];
int r, c;
int r2, c2;
int mov[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
bool isvalidBee(int x, int y)
{
if(!x || !y || x > n || y > n)
return false;
if(ma[x][y] == 'T' || ma[x][y] == 'D')
return false;
if(enj[x][y] != -1)
return false;
return true;
}
void BeeFS()
{
queue<pair<int, int> > q;
pair<int, int> act;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(ma[i][j] == 'H')
{
q.push({i, j});
}
else
enj[i][j] = -1;
}
}
while(!q.empty())
{
act = q.front();
q.pop();
for(int i = 0; i < 4; ++i)
{
int nx = act.first + mov[i][0];
int ny = act.second + mov[i][1];
if(isvalidBee(nx, ny))
{
enj[nx][ny] = enj[act.first][act.second] + s;
q.push({nx, ny});
}
}
}
}
bool isvalidMecho(int x, int y, int time)
{
if(!x || !y || x > n || y > n)
return false;
if(ma[x][y] == 'T')
return false;
if(ma[x][y] == 'D')
return true;
if(pa[x][y] != -1)
return false;
if(time >= enj[x][y])
return false;
return true;
}
bool monotone(int m)
{
queue<pair<int, int> > q;
pair<int, int> act;
for( int i = 1; i <= n; i++ )
for( int j = 1; j <= n; j++ )
pa[i][j] = -1;
q.push({r, c});
pa[r][c] = m * s;
if(enj[r][c] <= pa[r][c]) return false;
while(!q.empty())
{
act = q.front();
q.pop();
int time = pa[act.first][act.second] + 1;
for(int i = 0; i < 4; ++i)
{
int nx = act.first + mov[i][0];
int ny = act.second + mov[i][1];
if(isvalidMecho(nx, ny, time))
{
q.push({nx, ny});
pa[nx][ny] = time;
}
}
}
return pa[r2][c2] != -1;
}
int Binary(int a, int b)
{
while(a != b)
{
int m = (a + b) / 2 + 1;
if(monotone(m))
{
a = m;
}
else
b = m - 1;
}
return a;
}
int main()
{
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> s;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
cin >> ma[i][j];
if(ma[i][j] == 'M')
{
r = i, c = j;
}
if(ma[i][j] == 'D')
{
r2 = i, c2 = j;
}
}
}
BeeFS();
if(!monotone(0))
{
cout << "-1\n"; return 0;
}
cout << Binary(0, 640000);
return 0;
}
