#include <bits/stdc++.h>
using namespace std;
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define int long long
#define vi vector<int>
#define vb vector<bool>
#define vii vector<pair<int, int>>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define all(x) ((x).begin(), (x).end())
void solve()
{
int n, s;
cin >> n >> s;
vector<string> v(n);
for (auto &it : v)
cin >> it;
pii st;
pii en;
queue<pii> q;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
switch (v[i][j])
{
case 'M':
st.first = i;
st.second = j;
break;
case 'D':
en.first = i;
en.second = j;
break;
case 'H':
q.push({i, j});
}
}
}
vii dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
auto val = [&](int a, int b)
{
if (a < 0 || b < 0 || a >= n || b >= n)
return false;
return true;
};
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
if (v[x][y] == 'U')
break;
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dir[i].first;
int ny = y + dir[i].second;
if (val(nx, ny) && (v[nx][ny] == 'G' || v[nx][ny] == 'M'))
{
q.push({nx, ny});
v[nx][ny] = 'U';
}
}
}
int ans = -1;
int l = 0;
int r = (n * n + s - 1) / s;
while (l <= r)
{
int mid = (l + r) / 2;
vector<string> grid = v;
queue<pii> nq = q;
for (int i = 0; i < mid; i++)
{
queue<pii> tmp = nq;
while (!tmp.empty())
{
grid[tmp.front().first][tmp.front().second] = 'H';
tmp.pop();
}
while (!nq.empty())
{
int x = nq.front().first;
int y = nq.front().second;
if (grid[x][y] == 'U')
break;
nq.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dir[i].first;
int ny = y + dir[i].second;
if (val(nx, ny) && (grid[nx][ny] == 'G' || grid[nx][ny] == 'M'))
{
nq.push({nx, ny});
grid[nx][ny] = 'U';
}
}
}
}
queue<pii> bear;
bear.push(st);
vvi dis(n, vi(n, INT32_MAX));
dis[st.first][st.second] = 0;
bool flag = false;
while (1)
{
for (int i = 0; i < s; i++)
{
queue<pii> nbear;
while (!bear.empty())
{
int x = bear.front().first;
int y = bear.front().second;
bear.pop();
if (grid[x][y] == 'H')
continue;
for (int i = 0; i < 4; i++)
{
int nx = x + dir[i].first;
int ny = y + dir[i].second;
if (val(nx, ny) && grid[nx][ny] == 'G' || grid[nx][ny] == 'D' || grid[nx][ny] == 'U' && dis[nx][ny] == INT32_MAX)
{
nbear.push({nx, ny});
dis[nx][ny] = dis[x][y] + 1;
if (nx == en.first && ny == en.second)
{
flag = true;
break;
}
}
}
if (flag)
break;
}
bear = nbear;
}
if (bear.size() == 0)
break;
if (flag)
break;
queue<pii> tmp = nq;
while (!tmp.empty())
{
grid[tmp.front().first][tmp.front().second] = 'H';
tmp.pop();
}
while (!nq.empty())
{
int x = nq.front().first;
int y = nq.front().second;
if (grid[x][y] == 'U')
break;
nq.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dir[i].first;
int ny = y + dir[i].second;
if (val(nx, ny) && (grid[nx][ny] == 'G' || grid[nx][ny] == 'M'))
{
nq.push({nx, ny});
grid[nx][ny] = 'U';
}
}
}
}
if (flag)
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cout << ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
