#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> pi;
typedef pair<ll , ll> pll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define F first
#define S second
#define nd "\n"
#define forad(i , a , b) for(int i = a; i < (int) b; i++)
#define forat(i , a , b) for(int i = a; i >= b; i--)
#define debug(x) cout << #x << " = " << x << nd
#define debugv(x , s) cout << #x << " = " << forad(i , 0 , s) cout << x[i] << " "; cout << nd
#define faster ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define all(x) x.begin() , x.end()
const ll mod = 1e9+7 , INF = 1e9;
ll inv(ll x){return x <= 1 ? x : (mod - mod/x) * inv(mod%x) % mod;}
#define smod(a , b) (a%mod+b%mod)%mod
#define rmod(a , b) (a%mod - b%mod + mod)%mod
#define mmod(a , b) (a%mod) * (b%mod)%mod
#define dmod(a , b) (a%mod) * inv(b) %mod
int n, s;
vector<string> a;
queue<pi> q;
vvi dist;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
bool pasabee(int x , int y){
if (x < 0 || y < 0 || x >= n || y >= n) return false;
if (a[x][y] == 'T') return false;
if (a[x][y] == 'D') return false;
return true;
}
void ffbees() {
while (!q.empty()) {
pi front = q.front(); q.pop();
forad(d , 0 , 4){
int nx = front.F + dx[d], ny = front.S + dy[d];
if(!pasabee(nx , ny)) continue;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (dist[front.F][front.S] + 1 < dist[nx][ny]) {
dist[nx][ny] = dist[front.F][front.S] + 1;
q.push({nx, ny});
}
}
}
}
vvi bees(const vector<pi> ini) {
dist.assign(n, vi(n, INF));
while (!q.empty()) q.pop();
for (auto x : ini) {
dist[x.F][x.S] = 0;
q.push({x.F , x.S});
}
ffbees();
return dist;
}
bool cumple(int x, int y) {
if (x < 0 || y < 0 || x >= n || y >= n) return false;
return a[x][y] == 'G' || a[x][y] == 'M';
}
bool puedo(int mt, int bt) {return mt / s < bt;}
bool mechoff(int sx, int sy, int tx, int ty, const vvi bt, int w) {
dist.assign(n, vi(n, INF));
while (!q.empty()) q.pop();
if (bt[sx][sy] <= w) return false;
dist[sx][sy] = 0;
q.push({sx, sy});
while (!q.empty()) {
pi front = q.front(); q.pop();
int t = dist[front.F][front.S] + 1;
forad(d , 0 , 4) {
int nx = front.F + dx[d], ny = front.S + dy[d];
if(!cumple(nx , ny))continue;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (t >= dist[nx][ny]) continue;
int quedan = bt[nx][ny] - w;
if(quedan <= 0) continue;
if (puedo(t, quedan)) {
dist[nx][ny] = t;
q.push({nx, ny});
}
}
}
forad(d , 0 , 4) {
int nx = tx + dx[d], ny = ty + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (!cumple(nx, ny)) continue;
if (dist[nx][ny] == INF) continue;
if (puedo(dist[nx][ny], bt[nx][ny] - w)) return true;
}
return false;
}
int main() {
faster;
cin >> n >> s;
a.resize(n);
forad(i, 0, n) cin >> a[i];
int sx, sy, tx, ty;
vector<pi> ini;
forad(i, 0, n) {
forad(j, 0, n) {
if (a[i][j] == 'M') sx = i, sy = j;
if (a[i][j] == 'H') ini.pb({i, j});
if (a[i][j] == 'D') tx = i, ty = j;
}
}
vvi bt = bees(ini);
int l = 0, r = n * n , m;
while (l <= r) {
m = l + (r - l) / 2;
if (mechoff(sx, sy, tx, ty, bt, m)) l = m + 1;
else r = m - 1;
}
cout << r << nd;
}
