#include<bits/stdc++.h>
#define ll long long int
#define f first
// #define s second
using namespace std;
int di[4] = {0, 0, 1, -1};
int dj[4] = {-1, 1, 0, 0};
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, s;
cin >> n >> s;
vector<string> mat(n, "");
vector<vector<int>> time(n, vector<int>(n, 0));
int si, sj, ei, ej;
queue<pair<int,pair<int,int>>> bag;
vector<vector<bool>> v(n, vector<bool>(n, 0));
for (int i = 0 ; i < n ; i++) cin >> mat[i];
cout << -1;
// for (int i = 0 ; i < n ; i++) {
// for (int j = 0 ; j < n ; j++) {
// if (mat[i][j] == 'M') {
// si = i;
// sj = j;
// } else if (mat[i][j] == 'D') {
// ei = i;
// ej = j;
// } else if (mat[i][j] == 'H') {
// bag.push({0, {i, j}});
// v[i][j] = 1;
// }
// }
// }
// while(!bag.empty()) {
// int cnt = bag.front().first;
// int i = bag.front().second.first;
// int j = bag.front().second.second;
// bag.pop();
// for (int d = 0 ; d < 4 ; d++) {
// int nxi = i + di[d];
// int nxj = j + dj[d];
// if (nxi >= 0 && nxi < n && nxj >= 0 && nxj < n && mat[nxi][nxj] != 'T') {
// if (v[nxi][nxj]) continue;
// bag.push({cnt+1, {nxi, nxj}});
// v[nxi][nxj] = 1;
// time[nxi][nxj] = cnt+1;
// }
// }
// }
// // for (int i = 0 ; i < n ; i++) {
// // for (int j = 0 ; j < n ; j++) cout << time[i][j] << ' ';
// // cout << endl;
// // }
// int l = 0;
// int r = n*n;
// // bool valid = 0;
// vector<int> valid(n*n, 0);
// while(l < r) {
// int mid = (l+r+1)/2;
// // cout << mid << endl;
// if (mid >= time[si][sj]) r = mid-1;
// else {
// bag.push({mid*s, {si, sj}});
// v.resize(0);
// v.resize(n, vector<bool>(n, 0));
// v[si][sj] = 1;
// // cout << bag.size() << endl;
// while(!bag.empty()) {
// int cnt = bag.front().first;
// int i = bag.front().second.first;
// int j = bag.front().second.second;
// // cout << i << ' ' << j << ' ' << cnt << endl;
// bag.pop();
// if (i == ei && j == ej) {
// l = mid;
// valid[l] = 1;
// break;
// }
// for (int d = 0 ; d < 4 ; d++) {
// int nxi = i + di[d];
// int nxj = j + dj[d];
// if (nxi >= 0 && nxi < n && nxj >= 0 && nxj < n && mat[nxi][nxj] != 'T') {
// if (!v[nxi][nxj] && (cnt+1) / s < time[nxi][nxj]) {
// bag.push({cnt+1, {nxi, nxj}});
// v[nxi][nxj] = 1;
// }
// }
// }
// }
// if (bag.empty()) r = mid-1;
// else {
// while(!bag.empty()) {
// bag.pop();
// }
// }
// }
// }
// if (valid[l]) cout << l;
// else cout << -1;
}
