#include<bits/stdc++.h>
using namespace std ;
# define F first
# define S second
# define int long long
# define in insert
# define pb push_back
# define pob pop_back
# define INF INT_MAX
# define INFL 1e18 + 10
# define mod 1000000007
# define vi vector<int>
# define pii pair<int , int>
# define vvi vector< vector<int> >
# define vpi vector<pair<int, int>>
# define all(v) v.begin() , v.end()
# define debug(x) cerr << '\n' << #x << " = " << x << '\n' ;
# define rep( i , s , e ) for( int i = s ; i <= e ; i++ )
# define repR( i , e , s ) for( int i = e ; i >= s ; i-- )
# define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
# define endl "\n"
vvi mp(805, vi(805));
vector<array<int, 2>> hives;
array<int, 2> st, nd;
int n, s;
bool safe(int i, int j){
if(mp[i][j] == -2) return false;
if(j < n && j >= 0 && i < n && i >= 0) return true;
return false;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void attack(){
queue<array<int, 2>> q;
for(auto x : hives){
q.push(x);
}
while(!q.empty()){
array<int, 2> t = q.front(); q.pop();
rep(i, 0, 3){
int x = t[0] + dx[i];
int y = t[1] + dy[i];
if(safe(x, y)){
if(mp[x][y] == 0) mp[x][y] = mp[t[0]][t[1]] + 1, q.push({x, y});
}
}
}
}
bool is_can(int v){
queue<array<int, 2>> q, tmp;
vector<vector<bool>> vis(805, vector<bool>(805, false));
q.push(st);
if(mp[st[0]][st[1]] <= v) return false;
vis[st[0]][st[1]] = true;
int t = 0, b = 1;
while(!q.empty()){
array<int, 2> tt = q.front(); q.pop();
rep(i, 0, 3){
int x = tt[0] + dx[i];
int y = tt[1] + dy[i];
if(safe(x, y)&& !vis[x][y] && b + v < mp[x][y] ){
if(x == nd[0] && y == nd[1]) return true;
tmp.push({x, y});
}
}
if(q.empty()){
while(!tmp.empty()){
tt = tmp.front();
vis[tt[0]][tt[1]] = true;
q.push(tt); tmp.pop();
}
t++;
if(t == s) t = 0, b++;
}
}
return false;
}
void solve(){
cin >> n >> s;
rep(i, 0, n-1){
string a;
cin >> a;
rep(j, 0, n-1){
if(a[j] == 'T') mp[i][j] = -2;
else if(a[j] == 'M') st = {i, j};
else if(a[j] == 'H') mp[i][j] = 1, hives.pb({i, j});
else if(a[j] == 'D') nd = {i, j};
}
}
attack();
int l = 0, r = mp[st[0]][st[1]] + 1, res = 0;
while(l <= r){
int md = (l+r)>>1;
if(is_can(md)){
res = md;
l = md+1;
}else{
r = md-1;
}
}
if(res == 0) cout << -1 << endl;
else cout << res << endl;
}
signed main(){
solve();
return 0;
}
