#include<bits/stdc++.h>
#define mp make_pair
#define x first
#define y second

using namespace std;

int const maxn = 5005;
char a[maxn][maxn];
pair < int, int > dist[maxn][maxn];
int inf = 1e9 + 7;
vector < pair < int, int > > go = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
priority_queue < pair < pair < int, int >, pair < int, int > > > Q;
pair < int, int > up[maxn][maxn];

inline void upd(int i, int j, pair < int, int > d) {
    if (d < dist[i][j]) {
        dist[i][j] = d;
        Q.push({mp(-dist[i][j].x, -dist[i][j].y), {i, j}});
    }
}

main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            dist[i][j] = {inf, inf};
        }
    }
    dist[1][1] = {0, k};
    Q.push({{0, -k}, {1, 1}});
    for (int sum = 2 * n; sum >= 2; sum--) {
        for (int i = 1; i <= n; i++) {
            int j = sum - i;
            if (j < 1 || j > n) continue;
            up[i][j] = {-1, -1};
            int x = j + 1, y = i;
            if (x <= n) {
                if (a[x][y] == '.') up[i][j] = {x, y};
                else up[i][j] = up[x][y];
            }
        }
    }
    while (!Q.empty()) {
        pair <pair <int, int>, pair <int, int> > tt = Q.top();
        auto cur = mp(mp(-tt.x.x, -tt.x.y), tt.y);
        Q.pop();
        if (dist[cur.y.x][cur.y.y] != cur.x) continue;

        int x = cur.second.first, y = cur.second.second;
        int t = cur.first.first, s = cur.first.second;
        for (auto key : go) {
            int i = x + key.first, j = y + key.second;
            if (i >= 1 && j >= 1 && i <= n && j <= n && a[i][j] == '.') {
                upd(i, j, {t + 1, k});
            }
        }
        pair < int, int > nxt = up[x][y];
        if (nxt.first != -1) {
            int add_s = nxt.first + nxt.second - x - y;
            if (add_s + s <= k) upd(nxt.first, nxt.second, {t, s + add_s});
            else if (add_s <= k) upd(nxt.first, nxt.second, {t + 1, add_s});
        }
    }
    if (dist[n][n].first == inf) cout << -1 << '\n';
    else cout << dist[n][n].first << '\n';
    return 0;
}