#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using ii = pair<int, int>;
using ll = pair<lint, lint>;
using ti = tuple<int, int, int>;
using il = pair<int, lint>;
namespace T {
const int MAX = 1e5 + 5;
const int INF = 1e9 + 7;
const int N = 1e6 + 5;
int max_t[4 * MAX];
int min_t[4 * MAX];
void init() {
  for (int i = 0; i < 4 * MAX; i++) {
    max_t[i] = min_t[i] = 0;
  }
}
void max_up(int n, int s, int e, int p, int v) {
  if (p < s || p > e) return;
  if (s == e)
    max_t[n] = v;
  else {
    max_up(2 * n, s, (s + e) / 2, p, v);
    max_up(2 * n + 1, (s + e) / 2 + 1, e, p, v);
    max_t[n] = max(max_t[2 * n], max_t[2 * n + 1]);
  }
}
void min_up(int n, int s, int e, int p, int v) {
  if (p < s || p > e) return;
  if (s == e)
    min_t[n] = v;
  else {
    min_up(2 * n, s, (s + e) / 2, p, v);
    min_up(2 * n + 1, (s + e) / 2 + 1, e, p, v);
    min_t[n] = min(min_t[2 * n], min_t[2 * n + 1]);
  }
}
int max_v(int n, int s, int e, int l, int r) {
  if (r < s || l > e) return 0;
  if (l <= s && e <= r) return max_t[n];
  int m = (s + e) / 2;
  return max(max_v(2 * n, s, m, l, r), max_v(2 * n + 1, m + 1, e, l, r));
}
int min_v(int n, int s, int e, int l, int r) {
  if (r < s || l > e) return INF;
  if (l <= s && e <= r) return min_t[n];
  int m = (s + e) / 2;
  return min(min_v(2 * n, s, m, l, r), min_v(2 * n + 1, m + 1, e, l, r));
}
class fenwick {
 public:
  lint tree[N] = {
      0,
  };
  void update(int p, lint v) {
    while (p < N) {
      tree[p] += v;
      p += p & -p;
    }
  }
  lint sum(int p) {
    if (p == 0) {
      return 0LL;
    }
    lint ret = 0;
    while (p) {
      ret += tree[p];
      p -= p & -p;
    }
    return ret;
  }
  lint sum(int x, int y) { return sum(y) - sum(x - 1); }
};
}  // namespace T
namespace P {
const int N = 2 * 1e6 + 5;
using lint = long long;
bool v[N];
void make() {
  fill(v, v + N, true);
  for (int i = 2; i < N; i++) {
    if (v[i]) {
      for (lint j = (lint)i * i; j < N; j += i) {
        v[j] = false;
      }
    }
  }
}
}  // namespace P
namespace U {
int min3(int a, int b, int c) { return min(min(a, b), c); }
int min4(int a, int b, int c, int d) { return min(min(a, b), min(c, d)); }
int max3(int a, int b, int c) { return max(max(a, b), c); }
int max4(int a, int b, int c, int d) { return max(max(a, b), max(c, d)); }
bool get(char c) {
  return (c == 'a') || (c == 'e') || (c == 'i') || (c == 'o') || (c == 'u');
}
int gcd(int a, int b) {
  if (a < b) {
    swap(a, b);
  }
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
}  // namespace U
int n, k;
const int N = 505;
const int M = 250005;
char s[N][N];
bool vis[N][N];
int lab[N][N];
int num[M];
int a[M];
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int dfs(int x, int y, int cnt) {
  lab[x][y] = cnt;
  vis[x][y] = true;
  int r = 1;
  for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (0 <= nx && nx < n && 0 <= ny && ny < n) {
      if (!vis[nx][ny] && s[nx][ny] == '.') {
        r += dfs(nx, ny, cnt);
      }
    }
  }
  return r;
}
void input() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%s", s[i]);
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!vis[i][j] && s[i][j] == '.') {
        ++cnt;
        num[cnt] = dfs(i, j, cnt);
      }
    }
  }
}
void increase(int l, vector<int> &lnum, int &cnum) {
  if (lnum[l] == 0) {
    cnum += num[l];
  }
  ++lnum[l];
}
void decrease(int l, vector<int> &lnum, int &cnum) {
  if (lnum[l] == 1) {
    cnum -= num[l];
  }
  --lnum[l];
}
void go() {
  int ans = 0;
  for (int i = 0; i <= n - k; i++) {
    int dnum = 0;
    int cnum = 0;
    vector<int> lnum(M);
    for (int x = 0; x < k; x++) {
      for (int y = 0; y < k; y++) {
        if (s[i + x][y] == '.') {
          increase(lab[i + x][y], lnum, cnum);
        } else {
          ++dnum;
          for (int d = 0; d < 4; d++) {
            int nx = i + x + dx[d];
            int ny = y + dy[d];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
              increase(lab[nx][ny], lnum, cnum);
            }
          }
        }
      }
    }
    ans = max(ans, cnum + dnum);
    for (int j = k; j < n; j++) {
      for (int x = 0; x < k; x++) {
        if (s[i + x][j - k] == '.') {
          decrease(lab[i + x][j - k], lnum, cnum);
        } else {
          dnum--;
          for (int d = 0; d < 4; d++) {
            int nx = i + x + dx[d];
            int ny = j - k + dy[d];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
              decrease(lab[nx][ny], lnum, cnum);
            }
          }
        }
        if (s[i + x][j] == '.') {
          increase(lab[i + x][j], lnum, cnum);
        } else {
          ++dnum;
          for (int d = 0; d < 4; d++) {
            int nx = i + x + dx[d];
            int ny = j + dy[d];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
              increase(lab[nx][ny], lnum, cnum);
            }
          }
        }
      }
      ans = max(ans, cnum + dnum);
    }
  }
  printf("%d\n", ans);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  go();
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

You have a grid with n rows and n columns. Each cell is either empty (denoted by '.') or blocked (denoted by 'X').

Two empty cells are directly connected if they share a side. Two cells (r1, c1) (located in the row r1 and column c1) and (r2, c2) are connected if there exists a sequence of empty cells that starts with (r1, c1), finishes with (r2, c2), and any two consecutive cells in this sequence are directly connected. A connected component is a set of empty cells such that any two cells in the component are connected, and there is no cell in this set that is connected to some cell not in this set.

Your friend Limak is a big grizzly bear. He is able to destroy any obstacles in some range. More precisely, you can choose a square of size k × k in the grid and Limak will transform all blocked cells there to empty ones. However, you can ask Limak to help only once.

The chosen square must be completely inside the grid. It's possible that Limak won't change anything because all cells are empty anyway.

You like big connected components. After Limak helps you, what is the maximum possible size of the biggest connected component in the grid?

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 500) — the size of the grid and Limak's range, respectively.

Each of the next n lines contains a string with n characters, denoting the i-th row of the grid. Each character is '.' or 'X', denoting an empty cell or a blocked one, respectively.

Output

Print the maximum possible size (the number of cells) of the biggest connected component, after using Limak's help.

Examples

Input

5 2
..XXX
XX.XX
X.XXX
X...X
XXXX.


Output

10


Input

5 3
.....
.XXX.
.XXX.
.XXX.
.....


Output

25

Note

In the first sample, you can choose a square of size 2 × 2. It's optimal to choose a square in the red frame on the left drawing below. Then, you will get a connected component with 10 cells, marked blue in the right drawing.

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using ii = pair<int, int>;
using ll = pair<lint, lint>;
using ti = tuple<int, int, int>;
using il = pair<int, lint>;
namespace T {
const int MAX = 1e5 + 5;
const int INF = 1e9 + 7;
const int N = 1e6 + 5;
int max_t[4 * MAX];
int min_t[4 * MAX];
void init() {
  for (int i = 0; i < 4 * MAX; i++) {
    max_t[i] = min_t[i] = 0;
  }
}
void max_up(int n, int s, int e, int p, int v) {
  if (p < s || p > e) return;
  if (s == e)
    max_t[n] = v;
  else {
    max_up(2 * n, s, (s + e) / 2, p, v);
    max_up(2 * n + 1, (s + e) / 2 + 1, e, p, v);
    max_t[n] = max(max_t[2 * n], max_t[2 * n + 1]);
  }
}
void min_up(int n, int s, int e, int p, int v) {
  if (p < s || p > e) return;
  if (s == e)
    min_t[n] = v;
  else {
    min_up(2 * n, s, (s + e) / 2, p, v);
    min_up(2 * n + 1, (s + e) / 2 + 1, e, p, v);
    min_t[n] = min(min_t[2 * n], min_t[2 * n + 1]);
  }
}
int max_v(int n, int s, int e, int l, int r) {
  if (r < s || l > e) return 0;
  if (l <= s && e <= r) return max_t[n];
  int m = (s + e) / 2;
  return max(max_v(2 * n, s, m, l, r), max_v(2 * n + 1, m + 1, e, l, r));
}
int min_v(int n, int s, int e, int l, int r) {
  if (r < s || l > e) return INF;
  if (l <= s && e <= r) return min_t[n];
  int m = (s + e) / 2;
  return min(min_v(2 * n, s, m, l, r), min_v(2 * n + 1, m + 1, e, l, r));
}
class fenwick {
 public:
  lint tree[N] = {
      0,
  };
  void update(int p, lint v) {
    while (p < N) {
      tree[p] += v;
      p += p & -p;
    }
  }
  lint sum(int p) {
    if (p == 0) {
      return 0LL;
    }
    lint ret = 0;
    while (p) {
      ret += tree[p];
      p -= p & -p;
    }
    return ret;
  }
  lint sum(int x, int y) { return sum(y) - sum(x - 1); }
};
}  // namespace T
namespace P {
const int N = 2 * 1e6 + 5;
using lint = long long;
bool v[N];
void make() {
  fill(v, v + N, true);
  for (int i = 2; i < N; i++) {
    if (v[i]) {
      for (lint j = (lint)i * i; j < N; j += i) {
        v[j] = false;
      }
    }
  }
}
}  // namespace P
namespace U {
int min3(int a, int b, int c) { return min(min(a, b), c); }
int min4(int a, int b, int c, int d) { return min(min(a, b), min(c, d)); }
int max3(int a, int b, int c) { return max(max(a, b), c); }
int max4(int a, int b, int c, int d) { return max(max(a, b), max(c, d)); }
bool get(char c) {
  return (c == 'a') || (c == 'e') || (c == 'i') || (c == 'o') || (c == 'u');
}
int gcd(int a, int b) {
  if (a < b) {
    swap(a, b);
  }
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
}  // namespace U
int n, k;
const int N = 505;
const int M = 250005;
char s[N][N];
bool vis[N][N];
int lab[N][N];
int num[M];
int a[M];
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int dfs(int x, int y, int cnt) {
  lab[x][y] = cnt;
  vis[x][y] = true;
  int r = 1;
  for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (0 <= nx && nx < n && 0 <= ny && ny < n) {
      if (!vis[nx][ny] && s[nx][ny] == '.') {
        r += dfs(nx, ny, cnt);
      }
    }
  }
  return r;
}
void input() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%s", s[i]);
  }
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!vis[i][j] && s[i][j] == '.') {
        ++cnt;
        num[cnt] = dfs(i, j, cnt);
      }
    }
  }
}
void increase(int l, vector<int> &lnum, int &cnum) {
  if (lnum[l] == 0) {
    cnum += num[l];
  }
  ++lnum[l];
}
void decrease(int l, vector<int> &lnum, int &cnum) {
  if (lnum[l] == 1) {
    cnum -= num[l];
  }
  --lnum[l];
}
void go() {
  int ans = 0;
  for (int i = 0; i <= n - k; i++) {
    int dnum = 0;
    int cnum = 0;
    vector<int> lnum(M);
    for (int x = 0; x < k; x++) {
      for (int y = 0; y < k; y++) {
        if (s[i + x][y] == '.') {
          increase(lab[i + x][y], lnum, cnum);
        } else {
          ++dnum;
          for (int d = 0; d < 4; d++) {
            int nx = i + x + dx[d];
            int ny = y + dy[d];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
              increase(lab[nx][ny], lnum, cnum);
            }
          }
        }
      }
    }
    ans = max(ans, cnum + dnum);
    for (int j = k; j < n; j++) {
      for (int x = 0; x < k; x++) {
        if (s[i + x][j - k] == '.') {
          decrease(lab[i + x][j - k], lnum, cnum);
        } else {
          dnum--;
          for (int d = 0; d < 4; d++) {
            int nx = i + x + dx[d];
            int ny = j - k + dy[d];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
              decrease(lab[nx][ny], lnum, cnum);
            }
          }
        }
        if (s[i + x][j] == '.') {
          increase(lab[i + x][j], lnum, cnum);
        } else {
          ++dnum;
          for (int d = 0; d < 4; d++) {
            int nx = i + x + dx[d];
            int ny = j + dy[d];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
              increase(lab[nx][ny], lnum, cnum);
            }
          }
        }
      }
      ans = max(ans, cnum + dnum);
    }
  }
  printf("%d\n", ans);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  go();
}

```