#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"
int mp[801][801];
vector<array<int, 2>> hives;
int st[2], nd[2];
int n, s;
queue<array<int, 2>> q;
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(){
for(auto x : hives){
rep(i, 0, 3){
int k = x[0] + dx[i];
int y = x[1] + dy[i];
if(safe(k , y) && mp[k][y] != 1){
mp[k][y] = 1;
q.push({k, y});
}
}
}
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){
vector<vector<bool>> vis(805, vector<bool>(805, false));
q.push({st[0], st[1]});
if(mp[st[0]][st[1]] <= v) return false;
vis[st[0]][st[1]] = true;
int t = 1, b = 0, stp = 1, c = 0;
while(!q.empty()){
array<int, 2> tt = q.front(); q.pop(), t--;
rep(i, 0, 3){
int x = tt[0] + dx[i];
int y = tt[1] + dy[i];
if(x == nd[0] && y == nd[1]) return true;
if(safe(x, y)&& !vis[x][y] && stp + v <= mp[x][y] ){
if(c+1 == s && stp + v == mp[x][y]) continue;
b++;
q.push({x, y});
vis[x][y] = true;
}
}
if(t == 0){
t = b; c++; b = 0;
}
if(c >= s){
c = 0; stp++;
}
}
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[0] = i, st[1] = j;
else if(a[j] == 'H') mp[i][j] = 1, hives.pb({i, j});
else if(a[j] == 'D') mp[i][j] = -2, nd[0] = i, nd[1] = j;
}
}
attack();
int l = 0, r = 1e9, res = INF;
while(l <= r){
int md = (l+r)>>1;
queue<array<int, 2>> empty;
swap( q, empty );
if(is_can(md)){
res = md;
l = md+1;
}else{
r = md-1;
}
}
if(res == INF) cout << -1 << endl;
else cout << res << endl;
}
signed main(){
solve();
return 0;
}
