// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll cap = 1e3+1;
bool visited[cap][cap];
ll dist[cap][cap];
ll distmecho[cap][cap];
string grid[cap];
queue<pair<ll,ll>> q_multi;
queue<pair<ll,ll>> q;
ll n, s;
pair<ll,ll> m, d;
void multi_bfs(){
while(!q_multi.empty()){
pair<ll,ll> top = q_multi.front(); q_multi.pop();
ll y = top.first, x = top.second;
vector<pair<ll,ll>> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (auto dir: dirs){
ll dy = dir.first, dx = dir.second;
if (y+dy < 0 || x+dx < 0 || y+dy >= n || x + dx >= n) continue;
if (grid[y+dy][x+dx] == 'T' || grid[y+dy][x+dx] == 'D' || grid[y+dy][x+dx] == 'M') continue;
if (visited[y+dy][x+dx]) continue;
visited[y+dy][x+dx] = true;
dist[y+dy][x+dx] = dist[y][x] + 1;
q_multi.push({y+dy,x+dx});
}
}
}
void bfs(ll mid){
while(!q.empty()){
pair<ll,ll> top = q.front(); q.pop();
ll y = top.first, x = top.second;
vector<pair<ll,ll>> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (auto dir: dirs){
ll dy = dir.first, dx = dir.second;
if (y+dy < 0 || x + dx < 0 || y+dy >= n || x + dx >= n) continue;
if (grid[y+dy][x+dx] == 'T' || grid[y+dy][x+dx] == 'H') continue;
if (distmecho[y+dy][x+dx] != 1e18) continue;
if (grid[y+dy][x+dx] == 'D') {
distmecho[y+dy][x+dx] = distmecho[y][x] + 1;
return;
}
ll steps = distmecho[y][x] + 1;
ll minutes = (steps + s - 1) / s;
if (mid + minutes < dist[y+dy][x+dx]) {
distmecho[y+dy][x+dx] = steps;
q.push({y+dy, x+dx});
}
}
}
}
bool ok(ll mid){
if (mid >= dist[m.first][m.second]) return false;
for (ll i{}; i < n; i++){
for (ll j{}; j < n; j++){
distmecho[i][j] = 1e18;
}
}
while (!q.empty()) {
q.pop();
}
distmecho[m.first][m.second] = 0;
q.push(m);
bfs(mid);
return (!(distmecho[d.first][d.second] == (ll)1e18));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for (ll i{}; i < n; i++){
cin >> grid[i];
}
for (ll i{}; i < n; i++){
fill(dist[i], dist[i] + cap, 1e18);
fill(distmecho[i], distmecho[i] + cap, 1e18);
fill(visited[i], visited[i]+cap, false);
for (ll j{}; j < n; j++){
if (grid[i][j] == 'M') m = {i,j};
else if (grid[i][j] == 'H'){
q_multi.push({i,j});
dist[i][j] = 0;
visited[i][j] = true;
}
else if (grid[i][j] == 'D') d = {i,j};
}
}
multi_bfs();
ll l = 0, ans = -1;
ll r;
if (dist[m.first][m.second] >= (ll)1e17)
r = (ll)n * n;
else
r = dist[m.first][m.second] - 1;
while (l <= r){
ll mid = l + (r-l)/2;
if (ok(mid)){
ans = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
if (ans == -1){
cout << -1; return 0;
}
cout << ans+1;
}
