#include <bits/stdc++.h>
using namespace std;
using ll = long long; using db = double;
template <class T> using v = vector<T>;
using pii = pair<int, int>; using vi = v<int>; using vpi = v<pii>; using vvi = v<vi>; using vvpi = v<vpi>;
using pll = pair<ll, ll>; using vll = v<ll>; using vpl = v<pll>; using vvl = v<vll>; using vvpl = v<vpl>;
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
const int INF = 1e9;
const ll INFLL = 1e18;
const int N = 801;
int n, s, dist[N][N];
pii start, fin;
string grid[N];
bool vis[N][N];
vpi adjacent(int y, int x){
vpi adj;
if (y > 0){
if (grid[y-1][x] != 'H' && grid[y-1][x] != 'T') adj.pb({y-1, x});
}
if (x > 0){
if (grid[y][x-1] != 'H' && grid[y][x-1] != 'T') adj.pb({y, x-1});
}
if (y < n-1){
if (grid[y+1][x] != 'H' && grid[y+1][x] != 'T') adj.pb({y+1, x});
}
if (x < n-1){
if (grid[y][x+1] != 'H' && grid[y][x+1] != 'T') adj.pb({y, x+1});
}
return adj;
}
bool check(int t){
if (t*s >= dist[start.f][start.s]) return false;
vvi d(n, vi(n, 0));
v<v<bool>> processed(n, v<bool>(n, false));
d[start.f][start.s] = t * s;
processed[start.f][start.s] = true;
queue<pii> q;
q.push(start);
while (!q.empty()){
auto [y, x] = q.front(); q.pop();
for (auto [y1, x1] : adjacent(y, x)){
if (!processed[y1][x1] && d[y][x]+1 < dist[y1][x1]){
d[y1][x1] = d[y][x]+1;
processed[y1][x1] = true;
q.push({y1, x1});
}
}
}
return processed[fin.f][fin.s];
}
signed main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> s;
queue<pii> q;
for (int y=0; y<n; y++){
cin >> grid[y];
for (int x=0; x<n; x++){
dist[y][x] = INF;
if (grid[y][x] == 'M'){
start = {y, x};
}
else if (grid[y][x] == 'D'){
fin = {y, x};
}
else if (grid[y][x] == 'H'){
vis[y][x] = true;
q.push({y, x});
dist[y][x] = 0;
}
}
}
while (!q.empty()){
auto [y, x] = q.front(); q.pop();
for (auto [y1, x1] : adjacent(y, x)){
if (!vis[y1][x1] && grid[y1][x1] != 'D'){
vis[y1][x1] = true;
dist[y1][x1] = dist[y][x] + s;
q.push({y1, x1});
}
}
}
if (!check(0)){
cout << "-1\n";
}
else{
int l = 0, r = 1e9;
while (l < r){
int mid = (l+r+1)/2;
if (check(mid)) l = mid;
else r = mid-1;
}
cout << l << '\n';
}
return 0;
}
