#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using oset =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define vii vector<vector<int>>
#define vi vector<int>
#define v vector
#define pii pair<int, int>
#define mii map<int, int>
#define umii unordered_map<int, int>
#define si set<int>
#define usi unordered_set<int>
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"
#define pb push_back
#define MOD 1000000007
int inf = 1e9;
char arr[801][801];
int beesTime[801][801], mechotime[801][801];
int n, s;
array<int, 2> st, des;
vii temp = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool isValid(int i, int j) {return i >= 1 && j >= 1 && i <= n && j <= n;}
bool isFiss(int mid)
{
queue<array<int, 2>> q;
memset(beesTime, -1, sizeof beesTime);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (arr[i][j] == 'H') {
beesTime[i][j] = 0;
q.push({i, j});
}
}
}
while (!q.empty())
{
int i = q.front()[0], j = q.front()[1];
q.pop();
for (auto x : temp)
{
int ni = i+x[0], nj = j+x[1];
if (!isValid(ni, nj) || arr[ni][nj] == 'D' || arr[ni][nj] == 'T' || arr[ni][nj] == 'H' || beesTime[ni][nj] != -1) continue;
beesTime[ni][nj] = beesTime[i][j]+1;
q.push({ni, nj});
}
}
beesTime[des[0]][des[1]] = inf;
q.push(st);
memset(mechotime, -1, sizeof mechotime);
mechotime[st[0]][st[1]] = 0;
if (beesTime[st[0]][st[1]] <= mid) q.pop();
while (!q.empty())
{
int i = q.front()[0], j = q.front()[1];
q.pop();
if (i == des[0] && j == des[1]) return true;
for (auto x : temp)
{
int ni = i+x[0], nj = j+x[1];
if (!isValid(ni, nj) || arr[ni][nj] == 'H' || arr[ni][nj] == 'T' || mechotime[ni][nj] != -1) continue;
if (beesTime[ni][nj] <= ((mechotime[i][j]+1)/s)+mid) continue;
mechotime[ni][nj] = mechotime[i][j]+1;
q.push({ni, nj});
}
}
for (auto x : temp) {
int ni = x[0]+des[0], nj = x[1]+des[1];
if (!isValid(ni, nj)) continue;
if (mechotime[ni][nj] != -1 && mechotime[ni][nj]/s > beesTime[ni][nj]) return true;
}
return false;
}
void sol()
{
cin >> n >> s;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> arr[i][j];
if (arr[i][j] == 'M') st = {i, j};
if (arr[i][j] == 'D') des = {i, j};
}
}
int i = 0, j = n*n;
int ans = -1;
while (i <= j)
{
int mid = (i+j)/2;
if (isFiss(mid)) {
ans = mid;
i = mid+1;
}
else j = mid-1;
}
cout << ans;
}
signed main(){
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
// cin >> t;
t = 1;
while (t--)
sol();
// cerr << "Finished" << endl;
}
