#include <algorithm>
#include <cmath>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using ch = char;
using str = string;
#define pb push_back
#define elif else if
#define sz(C) (ll) C.size()
#define mp make_pair
#define mt make_tuple
#define flip(C) reverse(C.begin(), C.end())
#define ssort(C) sort(C.begin(), C.end())
#define rsort(C) sort(C.begin(), C.end(), greater<>())
#define FOR(x, e) for(ll x = 0; x < (ll) e; x++)
#define FORR(x, e) for(ll x = (ll) e - 1; x >= 0; x--)
#define FOB(x, b, e) for(auto x = b; x < e; x++)
#define FOI(x, e, i) for(ll x = 0; x < (ll) e; x += (ll) i)
#define FOBI(x, b, e, i) for(ll x = (ll) b; x < (ll) e; x += (ll) i)
#define FORE(x, C) for(auto &x : C)
#ifdef LOCAL
#include "tester.cpp"
#define main test_main
extern istringstream fin;
extern ostringstream fout;
string test_file_name = "tests";
#define cin fin
#define cout fout
#endif
vector<int> di { -1, 0, 1, 0};
vector<int> dj { 0, -1, 0, 1};
void fill_b(ll &n, vector<vector<char>> &g, queue<pair<ll, ll>> &bfs_b, vector<vector<ll>> &d_b) {
while(sz(bfs_b)) {
ll i0 = bfs_b.front().first, j0 = bfs_b.front().second;
bfs_b.pop();
FOR(k, 4) {
ll i1 = i0 + di[k], j1 = j0 + dj[k];
if(i1 < 0 || i1 >= n || j1 < 0 || j1 >= n) continue;
if(g[i1][j1] == 'T' || g[i1][j1] == 'D') continue;
if(d_b[i1][j1] != 1e18) continue;
d_b[i1][j1] = d_b[i0][j0] + 1;
bfs_b.push({i1, j1});
}
}
}
bool valid(ll &mid, ll &n, ll &s, vector<vector<ll>> &d_b, vector<vector<char>> &g, queue<pair<ll, ll>> bfs_m, vector<vector<ll>> d_m) {
while(sz(bfs_m)) {
ll i0 = bfs_m.front().first, j0 = bfs_m.front().second, d = d_m[i0][j0] + 1;
bfs_m.pop();
FOR(k, 4) {
ll i1 = i0 + di[k], j1 = j0 + dj[k];
if(i1 < 0 || i1 >= n || j1 < 0 || j1 >= n) continue;
if(g[i1][j1] == 'T') continue;
if(d_m[i1][j1] != 1e18) continue;
if(d_b[i1][j1] <= mid + d / s) continue;
if(g[i1][j1] == 'D') return true;
d_m[i1][j1] = d;
bfs_m.push({i1, j1});
}
}
return false;
}
int main() {
ll n, s, lo = 0;
cin >> n >> s;
ll hi = n * n;
vector<vector<char>> g(n, vector<char>(n));
vector<vector<ll>> d_b(n, vector<ll>(n, 1e18)), d_m(n, vector<ll>(n, 1e18));
queue<pair<ll, ll>> bfs_b, bfs_m;
FOR(i, n) FOR(j, n) {
cin >> g[i][j];
if(g[i][j] == 'H') {
bfs_b.push({i, j});
d_b[i][j] = 0;
}
elif(g[i][j] == 'M') {
bfs_m.push({i, j});
d_m[i][j] = 0;
}
}
fill_b(n, g, bfs_b, d_b);
if(!valid(lo, n, s, d_b, g, bfs_m, d_m)) {
cout << "-1\n";
return 0;
}
while(hi - lo > 0) {
ll mid = lo + (hi - lo + 1) / 2;
if(valid(mid, n, s, d_b, g, bfs_m, d_m)) lo = mid;
else hi = mid - 1;
}
cout << lo << '\n';
return 0;
}
