#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
using namespace std;
#define int long long
const int INF=1e18;
const int MAXN=801;
int n,s,ans=0;
string grid[MAXN];
int bee[MAXN][MAXN],dist[MAXN][MAXN];
vector<pair<int,int>> hives;
pair<int,int> start,dest;
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
bool inside(int x, int y) {
return (x > -1 && x < n && y > -1 && y < n && grid[x][y] != 'T' && grid[x][y]!='D');
}
void setIO(string name="") {
ios_base::sync_with_stdio(0); cin.tie(0);
if (!name.empty()) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
// check if after eating for t seconds,
// is it possible to reach the destination
bool check(int t)
{
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
dist[i][j]=INF;
queue<pair<int,int>>q;
if (bee[start.first][start.second]>t) q.push(start);
dist[start.first][start.second]=0;
while (!q.empty())
{
pair<int,int> c=q.front();
q.pop();
for (int i=0; i<4; i++)
{
int x=c.first+dx[i],y=c.second+dy[i];
// if i can usually get there in 7 step
// taking 2 steps a minute i can get there in ceil(7/2) steps
if (inside(x,y)&&dist[x][y]==INF&&(bee[x][y]-t)>(dist[c.first][c.second]+1)/s)
{
dist[x][y]=dist[c.first][c.second]+1;
q.push({x,y});
}
}
}
// cout << t << endl;
// for (int i=0; i<n; i++) {for (int j=0; j<n; j++) cout << dist[i][j] << " "; cout << endl;}
bool reached=false;
for (int i=0; i<4; i++)
{
int x=dest.first+dx[i],y=dest.second+dy[i];
if (inside(x,y)&&dist[x][y]!=INF&&(bee[x][y]-t)>(dist[x][y])/s)
reached=true;
}
return reached;
}
int32_t main()
{
cin >> n >> s;
for (int i=0; i<n; i++) cin >> grid[i];
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
{
if (grid[i][j]=='M') start={i,j};
if (grid[i][j]=='D') dest={i,j};
if (grid[i][j]=='H') hives.push_back({i,j});
bee[i][j]=INF;
}
// multisource bfs to find the distances of cells from hive
queue<pair<int,int>> q;
for (int i=0; i<hives.size(); i++) {
q.push(hives[i]);
bee[hives[i].first][hives[i].second]=0;
}
while (!q.empty())
{
pair<int,int> c=q.front();
q.pop();
for (int i=0; i<4; i++)
{
int x=c.first+dx[i],y=c.second+dy[i];
if (inside(x,y)&&grid[x][y]!='D'&&bee[x][y]==INF)
{
bee[x][y]=bee[c.first][c.second]+1;
q.push({x,y});
}
}
}
// for (int i=0; i<n; i++) {for (int j=0; j<n; j++) cout << bee[i][j] << " "; cout << endl;} cout << endl;
int lo=0,hi=n*n;
while (lo<=hi)
{
int mid=lo+(hi-lo)/2;
// cout << mid << endl;
if (check(mid))
{
ans=max(ans,mid);
lo=mid+1;
}
else hi=mid-1;
}
if (!check(0)) cout << -1 << endl;
else cout << ans << endl;
}
