// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define mp make_pair
#define f first
#define s second
#define pi pair<int, int>
#define endl '\n'
#ifdef LOCAL
#include "/mnt/c/yukon/pp.hpp"
#endif
vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, S;
cin >> n >> S;
vector<vector<int>> grid(n, vector<int>(n));
pi st, ed;
queue<array<int, 3>> q;
vector<vector<int>> bist(n, vector<int>(n, 9));
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < n; j++) {
if (s[j] == 'T') {
grid[i][j] = -1;
} else if (s[j] == 'G') {
grid[i][j] = 0;
} else if (s[j] == 'M') {
grid[i][j] = 0;
st = {i, j};
} else if (s[j] == 'D') {
grid[i][j] = 0;
ed = {i, j};
} else {
grid[i][j] = 1;
bist[i][j] = 0;
q.push({i, j, 0});
}
}
}
// dist from hives first
while (sz(q)) {
auto [i, j, di] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int ni = i + dx[d], nj = j + dy[d];
if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] != -1 && di + 1 < bist[ni][nj]) {
bist[ni][nj] = di + 1;
q.push({ni, nj, di + 1});
}
}
}
// for (int i = 0; i < n; i++) {
// cerr << bist[i] << endl;
// }
vector<vector<pi>> fastest(n, vector<pi>(n, {-inf, 0}));
fastest[st.f][st.s] = {bist[st.f][st.s], 1};
q.push({st.f, st.s, 0});
map<pi, pi> prev;
while (sz(q)) {
auto [i, j, d] = q.front();
q.pop();
// cout << "start from: " << i << ' ' << j << " with distance " << d << endl;
for (int dir = 0; dir < 4; dir++) {
int ni = i + dx[dir], nj = j + dy[dir];
int mins = (d + 1) / S;
if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] != -1) {
if (mins <= bist[ni][nj]) {
int best = min(fastest[i][j].f, bist[ni][nj] - mins);
if (best == -inf) {
// cout << "fastest[" << ni << "][" << nj << "] = {" << best << ", " << (bool)((d + 1) % S > 0) << "}" << endl;
fastest[ni][nj] = {bist[ni][nj] - mins, (d + 1) % S > 0};
prev[{ni, nj}] = {i, j};
q.push({ni, nj, d + 1});
} else if (best > fastest[ni][nj].f || (best == fastest[ni][nj].f && (d + 1) % S > fastest[ni][nj].s)) {
// cout << "fastest[" << ni << "][" << nj << "] = {" << best << ", " << (bool)((d + 1) % S > 0) << "}" << endl;
fastest[ni][nj] = {best, (d + 1) % S > 0};
prev[{ni, nj}] = {i, j};
q.push({ni, nj, d + 1});
}
}
}
}
}
// cout << "path:" << endl;
// auto tmp = ed;
// while (tmp != pi{0, 0}) {
// cout << tmp << endl;
// tmp = prev[tmp];
// }
cout << (fastest[ed.f][ed.s].f == -inf ? -1 : fastest[ed.f][ed.s].f - 1) << endl;
}
// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)
