#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


// [0, n), 1 <= n <= 2^(6D)
template <int D> struct Set {
  int n;
  vector<unsigned long long> a[D];
  Set() {}
  Set(int n_) : n(n_) {
    static_assert(1 <= D && D <= 6, "Set: 1 <= D <= 6 must hold");
    assert(1 <= n_ && n_ <= 1LL << (6 * D));
    for (int d = 0; d < D; ++d) {
      n_ = (n_ + 63) >> 6;
      a[d].assign(n_, 0);
    }
  }
  bool empty() const {
    return !a[D - 1][0];
  }
  bool contains(int x) const {
    return (a[0][x >> 6] >> (x & 63)) & 1;
  }
  void insert(int x) {
    for (int d = 0; d < D; ++d) {
      const int q = x >> 6, r = x & 63;
      a[d][q] |= 1ULL << r;
      x = q;
    }
  }
  void erase(int x) {
    for (int d = 0; d < D; ++d) {
      const int q = x >> 6, r = x & 63;
      if ((a[d][q] &= ~(1ULL << r))) break;
      x = q;
    }
  }
  // min s.t. >= x
  int next(int x) const {
    for (int d = 0; d < D; ++d) {
      const int q = x >> 6, r = x & 63;
      if (static_cast<size_t>(q) >= a[d].size()) break;
      const unsigned long long upper = a[d][q] >> r;
      if (upper) {
        x += __builtin_ctzll(upper);
        for (int e = d - 1; e >= 0; --e) x = x << 6 | __builtin_ctzll(a[e][x]);
        return x;
      }
      x = q + 1;
    }
    return n;
  }
  // max s.t. <= x
  int prev(int x) const {
    for (int d = 0; d < D; ++d) {
      if (x < 0) break;
      const int q = x >> 6, r = x & 63;
      const unsigned long long lower = a[d][q] << (63 - r);
      if (lower) {
        x -= __builtin_clzll(lower);
        for (int e = d - 1; e >= 0; --e) x = x << 6 | (63 - __builtin_clzll(a[e][x]));
        return x;
      }
      x = q - 1;
    }
    return -1;
  }
};


constexpr int DX[4] = {+1, 0, -1, 0};
constexpr int DY[4] = {0, +1, 0, -1};

int N, K;
char A[5010][5010];

Set<3> ss[10010];
int dist[5010][5010];

int main() {
  for (; ~scanf("%d%d", &N, &K); ) {
    for (int x = 1; x <= N; ++x) {
      scanf("%s", A[x] + 1);
      A[x][0] = A[x][N + 1] = '*';
      A[x][N + 2] = 0;
    }
    for (const int x : {0, N + 1}) {
      fill(A[x], A[x] + (N + 2), '*');
      A[x][N + 2] = 0;
    }
    
    // (N+1-x) + y = z
    for (int z = 2; z <= 2*N; ++z) {
      ss[z] = Set<3>(N + 1);
    }
    for (int x = 1; x <= N; ++x) for (int y = 1; y <= N; ++y) if (A[x][y] == '.') {
      ss[(N+1-x) + y].insert(x);
    }
    
    memset(dist, ~0, sizeof(dist));
    vector<pair<int, int>> que(N * N);
    int qb = 0, qe = 0;
    dist[1][1] = 0;
    que[qe++] = make_pair(1, 1);
    for (; qb != qe; ) {
      const int x = que[qb].first;
      const int y = que[qb].second;
      ++qb;
// cerr<<dist[x][y]<<": "<<x<<" "<<y<<endl;
      if (x == N && y == N) {
        break;
      }
      auto update = [&](int xx, int yy) -> void {
        if (!~dist[xx][yy]) {
          dist[xx][yy] = dist[x][y] + 1;
          que[qe++] = make_pair(xx, yy);
        }
      };
      for (int dir = 0; dir < 4; ++dir) {
        const int xx = x + DX[dir];
        const int yy = y + DY[dir];
        if (A[xx][yy] == '.') {
          update(xx, yy);
        }
      }
      auto check = [&](int x0, int y0) -> void {
        const int z = (N+1-x0) + y0;
        for (; ; ) {
          const int xx = ss[z].next(x0);
          if (xx > N) break;
          const int yy = z - (N+1-xx);
// cerr<<"  "<<x0<<" "<<y0<<" -> "<<xx<<" "<<yy<<endl;
          if (xx + yy > x + y + K) break;
          ss[z].erase(xx);
          update(xx, yy);
        }
      };
      check(x, y);
      check(y + 1, x);
    }
    
    printf("%d\n", dist[N][N]);
  }
  return 0;
}