#include <bits/stdc++.h>
using namespace std;

int arr[801][801], prefix[801][801];
int n, k;

bool check(int m){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(arr[i][j] <= m) prefix[i][j] = 1;
			else prefix[i][j] = 0;
			prefix[i][j] += prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
		}
	}
	int maxx = 0;
	for(int i = k; i <= n; i++){
		for(int j = k; j <= n; j++){
			maxx = max(maxx, prefix[i][j] - prefix[i - k][j] - prefix[i][j - k] + prefix[i - k][j - k]);
		}
	}
	if(maxx >= k * k - k * k / 2) return true;
	else return false;
}

int main(){
	cin >> n >> k;
	int minn = 2e9, maxx = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> arr[i][j];
			minn = min(minn, arr[i][j]);
			maxx = max(maxx, arr[i][j]);
		}
	}
	int l = minn, r = maxx;
	while(r - l > 0){
		int m = (l + r) / 2;
		if(check(m)) r = m;
		else l = m + 1;
	}
	cout << l << '\n';
}
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
struct position {
    int x, y;
};

int main() {
    int h, w;
    cin >> h >> w;
    position g = {0, 0};
    vector<string> a(h);
    vector<vector<int>> c(h, vector<int>(w, 1 << 30));
    vector<vector<position>> t(26);
    vector<bool> init(26, true);
    queue<position> q;
    for (auto i = 0; i < h; i++) cin >> a[i];
    for (auto i = 0; i < h; i++) {
        for (auto j = 0; j < w; j++) {
            if (a[i][j] == 'S') q.push({i, j}), c[i][j] = 0;
            if (a[i][j] == 'G') g = {i, j};
            if (a[i][j] - 'a' >= 0 and a[i][j] - 'a' < 26)
                t[a[i][j] - 'a'].push_back({i, j});
        }
    }
    while (not q.empty()) {
        auto p = q.front();
        q.pop();
        for (auto i = 0; i < 4; i++) {
            position n = {p.x + dx[i], p.y + dy[i]};
            if (n.x < 0 or n.x >= h or n.y < 0 or n.y >= w)
                continue;
            if (a[n.x][n.y] == '#') continue;
            if (c[n.x][n.y] <= c[p.x][p.y] + 1) continue;
            c[n.x][n.y] = c[p.x][p.y] + 1;
            if (a[n.x][n.y] != 'G') q.push(n);
        }
        auto index = a[p.x][p.y] - 'a';
        if (index >= 0 and index < 26 and init[index]) {
            init[index] = false;
            for (auto& elm : t[index]) {
                if (elm.x == p.x and elm.y == p.y) continue;
                if (c[elm.x][elm.y] <= c[p.x][p.y] + 1)
                    continue;
                c[elm.x][elm.y] = c[p.x][p.y] + 1;
                q.push(elm);
            }
        }
    }
    if (c[g.x][g.y] == 1 << 30) c[g.x][g.y] = -1;
    cout << c[g.x][g.y] << endl;
    return 0;
}