#include <iostream>
#include <array>
#include <string>
#include <queue>
const int MAX_N = 800 + 1;
const int INF = 1e9;
std::array<std::string, MAX_N> grid;
std::array<std::array<int, MAX_N>, MAX_N> minuteToBeHive, level;
void bfs(int n) {
std::queue<std::pair<int, int>> q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
minuteToBeHive[i][j] = INF;
if (grid[i][j] == 'H') {
q.push({i, j});
minuteToBeHive[i][j] = 0;
}
}
}
while (!q.empty()) {
auto v = q.front();
q.pop();
if (v.first > 0) {
if (grid[v.first - 1][v.second] == 'G' || grid[v.first - 1][v.second] == 'M') {
if (minuteToBeHive[v.first - 1][v.second] == INF)
q.push({v.first - 1, v.second});
minuteToBeHive[v.first - 1][v.second] = std::min(minuteToBeHive[v.first - 1][v.second], minuteToBeHive[v.first][v.second] + 1);
}
}
if (v.first < n - 1) {
if (grid[v.first + 1][v.second] == 'G' || grid[v.first + 1][v.second] == 'M') {
if (minuteToBeHive[v.first + 1][v.second] == INF)
q.push({v.first + 1, v.second});
minuteToBeHive[v.first + 1][v.second] = std::min(minuteToBeHive[v.first + 1][v.second], minuteToBeHive[v.first][v.second] + 1);
}
}
if (v.second > 0) {
if (grid[v.first][v.second - 1] == 'G' || grid[v.first][v.second - 1] == 'M') {
if (minuteToBeHive[v.first][v.second - 1] == INF)
q.push({v.first, v.second - 1});
minuteToBeHive[v.first][v.second - 1] = std::min(minuteToBeHive[v.first][v.second - 1], minuteToBeHive[v.first][v.second] + 1);
}
}
if (v.second < n - 1) {
if (grid[v.first][v.second + 1] == 'G' || grid[v.first][v.second + 1] == 'M') {
if (minuteToBeHive[v.first][v.second + 1] == INF)
q.push({v.first, v.second + 1});
minuteToBeHive[v.first][v.second + 1] = std::min(minuteToBeHive[v.first][v.second + 1], minuteToBeHive[v.first][v.second] + 1);
}
}
}
}
bool bfs2(int n, int s, int startMinute) {
std::pair<int, int> start, end;
std::queue<std::pair<int, int>> q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
level[i][j] = INF;
if (grid[i][j] == 'M')
start = {i, j};
if (grid[i][j] == 'D')
end = {i, j};
}
}
q.push(start);
level[start.first][start.second] = 0;
while (!q.empty()) {
auto v = q.front();
q.pop();
if (v.first > 0) {
if ((grid[v.first - 1][v.second] == 'G' || grid[v.first - 1][v.second] == 'D') && (startMinute + (level[v.first][v.second] + 1) / s < minuteToBeHive[v.first - 1][v.second])) {
if (level[v.first - 1][v.second] == INF)
q.push({v.first - 1, v.second});
level[v.first - 1][v.second] = std::min(level[v.first - 1][v.second], level[v.first][v.second] + 1);
}
}
if (v.first < n - 1) {
if ((grid[v.first + 1][v.second] == 'G' || grid[v.first + 1][v.second] == 'D') && (startMinute + (level[v.first][v.second] + 1) / s < minuteToBeHive[v.first + 1][v.second])) {
if (level[v.first + 1][v.second] == INF)
q.push({v.first + 1, v.second});
level[v.first + 1][v.second] = std::min(level[v.first + 1][v.second], level[v.first][v.second] + 1);
}
}
if (v.second > 0) {
if ((grid[v.first][v.second - 1] == 'G' || grid[v.first][v.second - 1] == 'D') && (startMinute + (level[v.first][v.second] + 1) / s < minuteToBeHive[v.first][v.second - 1])) {
if (level[v.first][v.second - 1] == INF)
q.push({v.first, v.second - 1});
level[v.first][v.second - 1] = std::min(level[v.first][v.second - 1], level[v.first][v.second] + 1);
}
}
if (v.second < n - 1) {
if ((grid[v.first][v.second + 1] == 'G' || grid[v.first][v.second + 1] == 'D') && (startMinute + (level[v.first][v.second] + 1) / s < minuteToBeHive[v.first][v.second + 1])) {
if (level[v.first][v.second + 1] == INF)
q.push({v.first, v.second + 1});
level[v.first][v.second + 1] = std::min(level[v.first][v.second + 1], level[v.first][v.second] + 1);
}
}
}
return level[end.first][end.second] != INF;
}
int solve(int n, int s) {
bfs(n);
int l = 0, r = n;
while (r - l > 1) {
int mid = (r + l) / 2;
if (bfs2(n, s, mid)) {
l = mid;
} else {
r = mid;
}
}
if (bfs2(n, s, l))
return l;
return -1;
}
int main() {
int n, s; std::cin >> n >> s;
for (int i = 0; i < n; ++i) {
std::cin >> grid[i];
}
std::cout << solve(n, s) << std::endl;
}
