#include "bits/stdc++.h"
using namespace std;
#define SorSufi namespace
#define ll long long
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#define lsb(x) (x & -x)
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
// #define cerr cout
#define int ll
#define endl '\n'
// #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
bool minimize(int &x, int y) { return x > y ? x = y, 1 : 0; }
bool maximize(int &x, int y) { return x < y ? x = y, 1 : 0; }
SorSufi Fexin{
vector<pii> d = {{0, 1},{0, -1},{1, 0},{-1, 0}};
struct Bee{int i, j, w;};
struct Mecho{int i, j, time, w;};
const int N = 8e2;
int n, l, bee[N + 5][N + 5], mecho[N + 5][N + 5], vs[N + 5][N + 5], vsIdx = 0, posI, posJ, disI, disJ;
char a[N + 5][N + 5];
bool valid(int i,int j){return i >= 1 && i <= n && j >= 1 && j <= n && vs[i][j] != vsIdx && a[i][j] != 'T';}
void buildBee(){
++vsIdx;
queue<Bee> q;
for (int i = 1; i <= n;++i)for (int j = 1; j <= n;++j)if(a[i][j] == 'H')q.push({i, j, 0});
while(q.size()){
Bee curr = q.front();q.pop();
if(vs[curr.i][curr.j] == vsIdx)continue;
vs[curr.i][curr.j] = vsIdx;
bee[curr.i][curr.j] = curr.w;
for(pii x : d){
int ni = curr.i + x.first, nj = curr.j + x.second;
if(valid(ni,nj))q.push({ni, nj, curr.w + 1});
}
}
}
void buildMecho(){
++vsIdx;
queue<Mecho> q;
for (int i = 1; i <= n;++i)for (int j = 1; j <= n;++j){
if(a[i][j] == 'M'){q.push({i, j, 0, 0});posI = i, posJ = j;}
if(a[i][j] == 'D')disI = i, disJ = j;
}
while(q.size()){
Mecho curr = q.front();q.pop();
if(vs[curr.i][curr.j] == vsIdx)continue;
mecho[curr.i][curr.j] = curr.w;
vs[curr.i][curr.j] = vsIdx;
for(pii x : d){
int ni = curr.i + x.first, nj = curr.j + x.second;
if(valid(ni, nj)){
int k = curr.time + 1;
q.push({ni, nj, k % l, curr.w + k / l});
}
}
}
}
bool valid(int x){
++vsIdx;
queue<Mecho> q;
q.push({posI, posJ, 0, 0});
while(q.size()){
Mecho curr = q.front();q.pop();
if(vs[curr.i][curr.j] == vsIdx || curr.w + x >= bee[curr.i][curr.j])continue;
if(curr.i == disI && curr.j == disJ)return 1;
vs[curr.i][curr.j] = vsIdx;
for(pii xx : d){
int ni = curr.i + xx.first, nj = curr.j + xx.second;
if(valid(ni,nj)){
int k = curr.time + 1;
int w = curr.w + k / l;
if(x + w < bee[ni][nj])
q.push({ni, nj, k % l, w});
}
}
}
return 0;
}
void Merlin(){
cin >> n >> l;
// ++l;
for (int i = 1; i <= n;++i)for (int j = 1; j <= n;++j)cin >> a[i][j];
buildBee();
buildMecho();
int lo = 0, hi = 69696969, mid, ans = -1;
while(lo <= hi){
mid = lo + hi >> 1;
if(valid(mid))
ans = mid, lo = mid + 1;
else hi = mid - 1;
}
cout << ans << endl;
// for (int i = 1; i <= n;++i){
// for (int j = 1; j <= n;++j)
// cout << bee[i][j] << " ";
// cout << endl;
// }
// cout << endl;
// for (int i = 1; i <= n;++i){
// for (int j = 1; j <= n;++j)
// cout << mecho[i][j] << " ";
// cout << endl;
// }
}
}
void Merlin() { Fexin::Merlin(); }
signed main(){
#define FILE_NAME "main"
ios_base::sync_with_stdio(0);cin.tie(0);
if (fopen(FILE_NAME ".in", "r")){
freopen(FILE_NAME ".in", "r", stdin);
freopen(FILE_NAME ".out", "w", stdout);
}
if (fopen(FILE_NAME ".inp", "r")){
freopen(FILE_NAME ".inp", "r", stdin);
freopen(FILE_NAME ".out", "w", stdout);
}
// int tc;cin >> tc;while(tc--)
Merlin();
// cerr << "TIME PROCCESS: " << TIME;
}
