#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion
using grid_t = vector<string>;
const vi32 dx = {1, -1, 0, 0};
const vi32 dy = {0, 0, 1, -1};
struct frac_t
{
int64_t enumer, denomin;
frac_t(int64_t e = 0, int64_t d = 1)
{
enumer = e;
denomin = d;
}
frac_t operator+(frac_t rhs)
{
int64_t d = lcm(denomin, rhs.denomin);
int64_t e = enumer * (d / denomin) + rhs.enumer * (d / rhs.denomin);
return {e, d};
}
bool operator<(frac_t rhs)
{
int64_t d = lcm(denomin, rhs.denomin);
return enumer * (d / denomin) < rhs.enumer * (d / rhs.denomin);
}
bool operator>=(frac_t rhs)
{
int64_t d = lcm(denomin, rhs.denomin);
return enumer * (d / denomin) >= rhs.enumer * (d / rhs.denomin);
}
bool operator<(int64_t rhs)
{
return *this < frac_t(rhs, 1);
}
bool operator>=(int64_t rhs)
{
return *this >= frac_t(rhs, 1);
}
double approx()
{
return (double)enumer / (double)denomin;
}
};
using bear_t = vector<vector<frac_t>>;
bool inside(p32 pos, int n)
{
return pos.first >= 0 && pos.first < n &&
pos.second >= 0 && pos.second < n;
}
void get_time(vp32 &hive, vvi32 &reach_time, grid_t &grid)
{
queue<p32> q;
for (auto &h : hive)
{
q.push(h);
reach_time[h.first][h.second] = 0;
}
while (!q.empty())
{
p32 cur = q.front();
q.pop();
for (int i = 0; i < (int)dx.size(); i++)
{
p32 next = {cur.first + dx[i], cur.second + dy[i]};
if (inside(next, (int)grid.size()) && grid[next.first][next.second] == 'M' &&
reach_time[next.first][next.second] == INT_MAX)
{
reach_time[next.first][next.second] = reach_time[cur.first][cur.second] + 1;
}
if (!inside(next, (int)grid.size()) ||
grid[next.first][next.second] != 'G' ||
reach_time[next.first][next.second] != INT_MAX)
{
continue;
}
reach_time[next.first][next.second] = reach_time[cur.first][cur.second] + 1;
q.push(next);
}
}
}
bool can_reach(p32 start, p32 end, int time, frac_t speed,
vvi32 &reach_time, bear_t &bear_time, grid_t &grid)
{
if (time >= reach_time[start.first][start.second])
{
return false;
}
bear_time[start.first][start.second] = frac_t(time, 1);
queue<p32> q;
q.push(start);
while (!q.empty())
{
p32 cur = q.front();
q.pop();
for (int i = 0; i < (int)dx.size(); i++)
{
p32 next = {cur.first + dx[i], cur.second + dy[i]};
frac_t cur_time = bear_time[cur.first][cur.second] + speed;
if (!inside(next, (int)grid.size()) ||
(grid[next.first][next.second] != 'G' &&
grid[next.first][next.second] != 'D') ||
bear_time[next.first][next.second].enumer != -1 ||
cur_time >= reach_time[next.first][next.second])
{
continue;
}
bear_time[next.first][next.second] = cur_time;
if (next == end)
{
return true;
}
q.push(next);
}
}
return false;
}
bool test_reach(p32 start, p32 end, int time, int s,
vvi32 &reach_time, bear_t &bear_time, grid_t &grid)
{
frac_t speed(1, s);
bool result = can_reach(start, end, time, speed, reach_time, bear_time, grid);
for (auto &row : bear_time)
{
for (auto &b : row)
{
b = frac_t(-1, 1);
}
}
return result;
}
int main()
{
#ifndef _AAAAAAAAA
ios_base::sync_with_stdio(false);
cin.tie(0);
#else
freopen("mecho.in", "r", stdin);
#ifndef __linux__
atexit([]()
{
freopen("con", "r", stdin);
system("pause"); });
#endif
#endif
int n, s;
cin >> n >> s;
grid_t grid(n);
vp32 hive;
p32 start, end;
{
int i = 0;
for (auto &row : grid)
{
cin >> row;
for (int j = 0; j < (int)row.size(); j++)
{
switch (row[j])
{
case 'M':
{
start = {i, j};
break;
}
case 'D':
{
end = {i, j};
break;
}
case 'H':
{
hive.emplace_back(i, j);
break;
}
}
}
i++;
}
}
vvi32 reach_time(n, vi32(n, INT_MAX));
bear_t bear_time(n, vector<frac_t>(n, frac_t(-1, -1)));
get_time(hive, reach_time, grid);
int result = 0;
for (int bit = 29; bit >= 0; bit--)
{
int cur = result + (1 << bit);
if (cur > n * n || !test_reach(start, end, cur, s, reach_time, bear_time, grid))
{
continue;
}
result = cur;
}
if (!result)
{
bool cant = !test_reach(start, end, 0, s, reach_time, bear_time, grid);
result = cant ? -1 : result;
}
cout << result << '\n';
return 0;
}
