Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is square-shaped consisting of $n$ rows and $n$ columns of square cells. The rows are numbered from $1$ to $n$, from top to bottom, and the columns are numbered from $1$ to $n$, from left to right. The position of a cell at row $r$ and column $c$ is represented as $(r, c)$. There are only two colors for the cells in cfpaint — black and white.

There is a tool named eraser in cfpaint. The eraser has an integer size $k$ ($1 \le k \le n$). To use the eraser, Gildong needs to click on a cell $(i, j)$ where $1 \le i, j \le n - k + 1$. When a cell $(i, j)$ is clicked, all of the cells $(i', j')$ where $i \le i' \le i + k - 1$ and $j \le j' \le j + k - 1$ become white. In other words, a square with side equal to $k$ cells and top left corner at $(i, j)$ is colored white.

A white line is a row or a column without any black cells.

Gildong has worked with cfpaint for some time, so some of the cells (possibly zero or all) are currently black. He wants to know the maximum number of white lines after using the eraser exactly once. Help Gildong find the answer to his question.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$) — the number of rows and columns, and the size of the eraser.

The next $n$ lines contain $n$ characters each without spaces. The $j$-th character in the $i$-th line represents the cell at $(i,j)$. Each character is given as either 'B' representing a black cell, or 'W' representing a white cell.


-----Output-----

Print one integer: the maximum number of white lines after using the eraser exactly once.


-----Examples-----
Input
4 2
BWWW
WBBW
WBBW
WWWB

Output
4

Input
3 1
BWB
WWB
BWB

Output
2

Input
5 3
BWBBB
BWBBB
BBBBB
BBBBB
WBBBW

Output
2

Input
2 2
BW
WB

Output
4

Input
2 1
WW
WW

Output
4



-----Note-----

In the first example, Gildong can click the cell $(2, 2)$, then the working screen becomes: BWWW

WWWW

WWWW

WWWB



Then there are four white lines — the $2$-nd and $3$-rd row, and the $2$-nd and $3$-rd column.

In the second example, clicking the cell $(2, 3)$ makes the $2$-nd row a white line.

In the third example, both the $2$-nd column and $5$-th row become white lines by clicking the cell $(3, 2)$.

Difficulty: interview

Starter code:

Solutions:
import sys


def count(n, k, field):
    blank = 0
    cnt = [[0] * (n - k + 1) for _ in range(n)]
    for i, row in enumerate(field):
        l = row.find('B')
        r = row.rfind('B')
        if l == r == -1:
            blank += 1
            continue
        if r - l + 1 > k:
            continue
        kl = max(0, r - k + 1)
        kr = min(l + 1, n - k + 1)
        cnt[i][kl:kr] = [1] * (kr - kl)

    acc = [[0] * (n - k + 1) for _ in range(n - k + 1)]
    t_cnt = list(zip(*cnt))
    for i, col in enumerate(t_cnt):
        aci = acc[i]
        tmp = sum(col[n - k:])
        aci[n - k] = tmp
        for j in range(n - k - 1, -1, -1):
            tmp += col[j]
            tmp -= col[j + k]
            aci[j] = tmp

    return blank, acc


n, k = list(map(int, input().split()))
field = [line.strip() for line in sys.stdin]
bh, hor = count(n, k, field)
t_field = [''.join(col) for col in zip(*field)]
bv, t_var = count(n, k, t_field)
var = list(zip(*t_var))

print(bh + bv + max(h + v for (rh, rv) in zip(hor, var) for (h, v) in zip(rh, rv)))


n,k=map(int,input().split())
board=[input() for _ in range(n)]
columns=[[0]*n for _ in range(n)]
rows=[[0]*n for _ in range(n)]
whites=0
for i in range(n):
  first=-1
  last=0
  flag=False
  for pos in range(n):
    if flag==False:
      if board[i][pos]=='B':
        first=pos
        flag=True
    else:
      if board[i][pos]=='B':
        last=pos
  if first==-1:
    whites+=1
    continue
  if last==0:
    last=first
  if last-first<k:
    for j in range(max(0,last-k+1),first+1):
      columns[i][j]+=1
for i in range(n):
  first=-1
  last=0
  flag=False
  for pos in range(n):
    if flag==False:
      if board[pos][i]=='B':
        first=pos
        flag=True
    else:
      if board[pos][i]=='B':
        last=pos
  if first==-1:
    whites+=1
    continue
  if last==0:
    last=first
  if last-first<k:
    for j in range(max(0,last-k+1),first+1):
      rows[j][i]+=1
ccounts=[[0]*n for _ in range(n)]
rcounts=[[0]*n for _ in range(n)]
for i in range(n):
  tmp=0
  for j in range(k):
    tmp+=columns[j][i]
  ccounts[0][i]=tmp
  for j in range(1,n-k+1):
    tmp+=columns[j+k-1][i]
    tmp-=columns[j-1][i]
    ccounts[j][i]=tmp
for i in range(n):
  tmp=0
  for j in range(k):
    tmp+=rows[i][j]
  rcounts[i][0]=tmp
  for j in range(1,n-k+1):
    tmp+=rows[i][j+k-1]
    tmp-=rows[i][j-1] 
    rcounts[i][j]=tmp
ans=whites
for x in range(n):
  for y in range(n):
    tmp=whites
    tmp+=ccounts[x][y]
    tmp+=rcounts[x][y]
    ans=max(ans,tmp)
print(ans)

from sys import stdin, stdout
from collections import *
from array import *
def iarr(delim = " "): return map(int, input().split(delim))
def mat(n, m, v = None): return [[v]*m for _ in range(n)]

n, k, *_ = iarr()
lc = [-1]*n
rc = [n]*n
tr = [-1]*n
br = [n]*n
b = [input() for _ in range(n)]
ans = mat(n, n, 0)
pre, post = 0, 0

for i, r in enumerate(b):
    for j, c in enumerate(r):
        if c == 'B':
            rc[i], br[j] = j, i
            if lc[i] == -1: lc[i] = j
            if tr[j] == -1: tr[j] = i
            
for i in range(n):
    if tr[i] == -1 and br[i] == n: pre += 1
    if lc[i] == -1 and rc[i] == n: pre += 1

for col in range(n-k+1):
    tot = 0
    for row in range(k):
        if lc[row] >= col and rc[row] < col+k: tot += 1
    ans[0][col] = tot
    for row in range(1, n-k+1):
        if lc[row-1] >= col and rc[row-1] < col+k: tot -= 1
        if lc[row+k-1] >= col and rc[row+k-1] < col+k: tot += 1
        ans[row][col] = tot

for row in range(n-k+1):
    tot = 0
    for col in range(k):
        tot += 1 if tr[col] >= row and br[col] < row+k else 0
    post = max(post, ans[row][0]+tot)
    for col in range(1, n-k+1):
        if tr[col-1] >= row and br[col-1] < row+k: tot -= 1
        if tr[col+k-1] >= row and br[col+k-1] < row+k: tot += 1
        post = max(post, ans[row][col]+tot)

print(pre+post)

n, k, *_ = map(int, input().split(" "))
lc = [-1]*n
rc = [n]*n
tr = [-1]*n
br = [n]*n
b = [input() for _ in range(n)]
ans = [[0]*n for _ in range(n)]
pre, post = 0, 0

for i in range(n):
    for j in range(n):
        if b[i][j] == 'B':
            rc[i], br[j] = j, i
            if lc[i] == -1:
                lc[i] = j
            if tr[j] == -1:
                tr[j] = i
for i in range(n):
    if tr[i] == -1 and br[i] == n:
        pre += 1
    if lc[i] == -1 and rc[i] == n:
        pre += 1

for col in range(n-k+1):
    tot = 0
    for row in range(k):
        if lc[row] >= col and rc[row] < col+k:
            tot += 1
    ans[0][col] = tot
    for row in range(1, n-k+1):
        if lc[row-1] >= col and rc[row-1] < col+k:
            tot -= 1
        if lc[row+k-1] >= col and rc[row+k-1] < col+k:
            tot += 1
        ans[row][col] = tot
for row in range(n-k+1):
    tot = 0
    for col in range(k):
        if tr[col] >= row and br[col] < row+k:
            tot += 1 
    post = max(post, ans[row][0]+tot)
    for col in range(1, n-k+1):
        if tr[col-1] >= row and br[col-1] < row+k:
            tot -= 1
        if tr[col+k-1] >= row and br[col+k-1] < row+k:
            tot += 1
        post = max(post, ans[row][col]+tot)

print(pre+post)

import sys
input = sys.stdin.readline

n,k=list(map(int,input().split()))

MAP=[input().strip() for i in range(n)]


MINR=[1<<30]*n
MAXR=[-1]*n
MINC=[1<<30]*n
MAXC=[-1]*n

for i in range(n):
    for j in range(n):
        if MAP[i][j]=="B":
            MINR[i]=min(MINR[i],j)
            MAXR[i]=max(MAXR[i],j)
            MINC[j]=min(MINC[j],i)
            MAXC[j]=max(MAXC[j],i)

ALWAYS=0
for i in range(n):
    if MINR[i]==1<<30 and MAXR[i]==-1:
        ALWAYS+=1
    if MINC[i]==1<<30 and MAXC[i]==-1:
        ALWAYS+=1

ANS=[[0]*(n-k+1) for i in range(n-k+1)]

for j in range(n-k+1):
    NOW=0
    for i in range(k):

        if j<=MINR[i] and j+k-1>=MAXR[i] and MINR[i]!=1<<30 and MAXR[i]!=-1:
            NOW+=1

    ANS[0][j]+=NOW

    for i in range(n-k):

        if j<=MINR[i] and j+k-1>=MAXR[i] and MINR[i]!=1<<30 and MAXR[i]!=-1:
            NOW-=1


        if j<=MINR[i+k] and j+k-1>=MAXR[i+k] and MINR[i+k]!=1<<30 and MAXR[i+k]!=-1:
            NOW+=1

        ANS[i+1][j]+=NOW

for i in range(n-k+1):
    NOW=0
    for j in range(k):

        if i<=MINC[j] and i+k-1>=MAXC[j] and MINC[j]!=1<<30 and MAXC[j]!=-1:
            NOW+=1

    ANS[i][0]+=NOW

    for j in range(n-k):

        if i<=MINC[j] and i+k-1>=MAXC[j] and MINC[j]!=1<<30 and MAXC[j]!=-1:
            NOW-=1

        if i<=MINC[j+k] and i+k-1>=MAXC[j+k] and MINC[j+k]!=1<<30 and MAXC[j+k]!=-1:
            NOW+=1

        ANS[i][j+1]+=NOW

print(max([max(a) for a in ANS])+ALWAYS)
        
        
        


def main():
  n, k = list(map(int, input().split()))
  ss = []
  tate = [[0 for _ in range(n+1)] for _ in range(n+1)]
  yoko = [[0 for _ in range(n+1)] for _ in range(n+1)]
  for i in range(n):
    s = input().strip()
    for j, _s in enumerate(s):
      tate[i+1][j+1] = tate[i][j+1] + (1 if _s == 'B' else 0)
      yoko[i+1][j+1] = yoko[i+1][j] + (1 if _s == 'B' else 0)
  lc = 0
  for i in range(n):
    if tate[n][i+1] == 0:
      lc += 1
    if yoko[i+1][n] == 0:
      lc += 1
  yans = [[0 for _ in range(n+1)] for _ in range(n+1)]
  tans = [[0 for _ in range(n+1)] for _ in range(n+1)]
  for i in range(n):
    l, r = 0, k
    while r <= n:
      yans[i+1][l+1] = yans[i][l+1]
      if yoko[i+1][n] != 0 and yoko[i+1][r] - yoko[i+1][l] == yoko[i+1][n]:
        yans[i+1][l+1] += 1
      l += 1
      r += 1

  for i in range(n):
    l, r = 0, k
    while r <= n:
      tans[l+1][i+1] = tans[l+1][i]
      if tate[n][i+1] != 0 and tate[r][i+1] - tate[l][i+1] == tate[n][i+1]:
        tans[l+1][i+1] += 1
      l += 1
      r += 1

  ans = lc
  for i in range(n-k+1):
    for j in range(n-k+1):
      ans = max(ans, lc+yans[i+k][j+1]-yans[i][j+1]+tans[i+1][j+k]-tans[i+1][j])
  # print(*tate, sep='\n')
  # print()
  # print(*yoko, sep='\n')
  # print()
  # print(*tans, sep='\n')
  # print()
  # print(*yans, sep='\n')
  # print()
  print(ans)


def __starting_point():
  main()

__starting_point()

n,k=map(int,input().split())
s=[]
for i in range(n):
	s+=[input()]
y=[[n,0] for i in range(n)]
z=[[n,0] for i in range(n)]
r=0
for i in range(n):
	ind1=n
	ind2=-1
	for j in range(n):
		if s[i][j]=='B':
			ind1=min(j,ind1)
			ind2=max(j,ind2)
	if ind1!=n:
		y[i]=[max(0,ind2+1-k),ind1]
	else:
		r+=1
for j in range(n):
	ind1=n
	ind2=-1
	for i in range(n):
		if s[i][j]=='B':
			ind1=min(i,ind1)
			ind2=max(i,ind2)
	if ind1!=n:
		z[j]=[max(0,ind2+1-k),ind1]
	else:
		r+=1
x=[[0 for i in range(n)] for i in range(n+1)]
x2=[[0 for i in range(n+1)] for i in range(n)]
for a in range(n):
	for b in range(n):
		i=n-1-a
		j=n-1-b
		x[i][j]+=x[i+1][j]
		if y[i][0]<=j<=y[i][1]:
			x[i][j]+=1
		if i+k<=n-1 and y[i+k][0]<=j<=y[i+k][1]:
			x[i][j]-=1
for b in range(n):
	for a in range(n):
		i=n-1-a
		j=n-1-b
		x2[i][j]+=x2[i][j+1]
		if z[j][0]<=i<=z[j][1]:
			x2[i][j]+=1
		if j+k<=n-1 and z[j+k][0]<=i<=z[j+k][1]:
			x2[i][j]-=1
m=0
for i in range(n):
	for j in range(n):
		c=x[i][j]+x2[i][j]
		if c>m:
			m=c
print(m+r)

import math
import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    n, k = list(map(int, input().split()))
    grid = [[] for _ in range(n)]
    for i in range(n):
        grid[i] = list(input().strip())
    row_min = [math.inf] * n
    row_max = [math.inf] * n
    col_min = [math.inf] * n
    col_max = [math.inf] * n
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 'B':
                row_min[i] = min(row_min[i], j)
                row_max[i] = j

            if grid[j][i] == 'B':
                col_min[i] = min(col_min[i], j)
                col_max[i] = j

    res = 0
    for r in range(n):
        if row_min[r] == math.inf:
            res += 1
    for c in range(n):
        if col_min[c] == math.inf:
            res += 1

    rows_plus = [[0 for _ in range(n)] for _ in range(n)]
    for c in range(n-k+1):
        added = 0
        for r in range(k):
            if row_min[r] >= c and row_max[r] <= c + k - 1:
                added += 1
        rows_plus[0][c] = added
        r = 1
        while r + k - 1 < n:
            if row_min[r-1] >= c and row_max[r-1] <= c + k - 1:
                added -= 1
            if row_min[r+k-1] >= c and row_max[r+k-1] <= c+k-1:
                added += 1
            rows_plus[r][c] = added
            r += 1

    cols_plus = [[0 for _ in range(n)] for _ in range(n)]
    for r in range(n-k+1):
        added = 0
        for c in range(k):
            if col_min[c] >= r and col_max[c] <= r + k - 1:
                added += 1
        cols_plus[r][0] = added
        c = 1
        while c + k - 1 < n:
            if col_min[c-1] >= r and col_max[c-1] <= r + k - 1:
                added -= 1
            if col_min[c+k-1] >= r and col_max[c+k-1] <= r+k-1:
                added += 1
            cols_plus[r][c] = added
            c += 1
    max_added = 0
    for r in range(n):
        for c in range(n):
            max_added = max(max_added, rows_plus[r][c] + cols_plus[r][c])

    print(res+max_added)


def __starting_point():
    main()

__starting_point()

from sys import stdin
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: list(map(int, rd().strip().split()))


n,k = rrd()

s = []
cal = [[0]*(n+10) for _i in range(n+10)]

for i in range(n):
    s.append(str(rd()))

ans = 0

for i in range(n):
    j = 0
    while j < n and s[i][j] == 'W':
        j += 1
    l = j

    if j >= n:
        ans += 1
        continue

    j = n-1
    while j >= 0 and s[i][j] == 'W':
        j -= 1
    r = j

    if r - l + 1 > k:
        continue

    l1 = max(0,i - k + 1)
    r1 = i + 1
    l2 = max(0,r - k + 1)
    r2 = l + 1

    cal[l1][l2] += 1
    cal[r1][l2] -= 1
    cal[l1][r2] -= 1
    cal[r1][r2] += 1


for i in range(n):
    j = 0
    while j < n and s[j][i] == 'W':
        j += 1
    l = j

    if j >= n:
        ans += 1
        continue

    j = n-1
    while j >= 0 and s[j][i] == 'W':
        j -= 1
    r = j

    if r-l+1 > k:
        continue

    l1 = max(0,i - k + 1)
    r1 = i + 1
    l2 = max(0,r - k + 1)
    r2 = l + 1

    cal[l2][l1] += 1
    cal[l2][r1] -= 1
    cal[r2][l1] -= 1
    cal[r2][r1] += 1

for i in range(n):
    for j in range(n):
        if j:
            cal[i][j] += cal[i][j-1]


pans = 0

for j in range(n):
    for i in range(n):
        if i:
            cal[i][j] += cal[i-1][j]
        pans = max(pans,cal[i][j])



print(ans+pans)




n, k = map(int, input().split())
a = [input() for _ in range(n)]
m = n - k + 1

def solve(a):
    p = [(r.find('B'), r.rfind('B')) for r in a]
    get = lambda i, j: j <= p[i][0] and p[i][1] <= j + k - 1
    res = [[0] * m for _ in range(m)]
    for j in range(m):
        res[0][j] = cnt = sum(x == -1 for x, _ in p) + sum(get(i, j) for i in range(k))
        for i in range(k, n):
            res[i - k + 1][j] = cnt = cnt + get(i, j) - get(i - k, j)
    return res

x = [v for r in solve(a) for v in r]
y = [v for r in list(zip(*solve(list(''.join(y) for y in zip(*a))))) for v in r]
print(max(u + v for u, v in zip(x, y)))

n, k = list(map(int, input().split()))
a = [input() for _ in range(n)]

# n, k = 5, 3
# a =["BWBBB",
# 	"BWBBB",
# 	"BBBBB",
# 	"BBBBB",
# 	"WBBBW"]
# n, k = 4, 2
# a =["BWWW",
# 	"WBBW",
# 	"WBBW",
# 	"WWWB"]

m = n - k + 1

def solve(a):
	p = [(r.find("B"), r.rfind("B")) for r in a]
	get = lambda i, j: j <= p[i][0] and p[i][1] <= j + k -1
	res = [[0]*m for i in range(m)]

	for j in range(m):
		res[0][j] = cnt = sum(x ==- 1 for x, _ in p) + sum(get(i, j) for i in range(k))

		for i in range(k, n):
			res[i -k + 1][j] = cnt = cnt + get(i, j) - get(i - k, j)
	return res

x = [v for r in solve(a) for v in r]
y = [v for r in list(zip(*solve(list(''.join(y) for y in zip(*a))))) for v in r]
print(max(u+v for u, v in zip(x, y)))


n, k = list(map(int, input().split()))
s = [input() for _ in range(n)]
g_row = [[] for _ in range(n)]
g_col = [[] for _ in range(n)]

already_white_line_nums = 0
for i in range(n):
    for j in range(n):
        if s[i][j] == 'B':
            g_row[i].append(j)
            g_col[j].append(i)

for i in range(n):
    if not g_row[i]:
        already_white_line_nums += 1
    # else:
    #     g_row[i] = g_row[i][0], g_row[i][-1]
    if not g_col[i]:
        already_white_line_nums += 1
    # else:
    #     g_col[i] = g_col[i][0], g_col[i][-1]

r = 0

new_white_line_nums_col = [[[0] for _ in range(n - k + 1)] for _ in range(n - k + 1)]
# new_white_line_nums_row = [[[0] for _ in range(n - k + 1)] for _ in range(n - k + 1)]

for i in range(n - k + 1):
    new_white_line_nums = 0
    for l in range(0, k):
        if g_col[l] and i <= g_col[l][0] and g_col[l][-1] < i + k:
            new_white_line_nums += 1
    new_white_line_nums_col[i][0] = new_white_line_nums

    for old_col in range(n - k):
        if g_col[old_col] and i <= g_col[old_col][0] and g_col[old_col][-1] < i + k:
            new_white_line_nums -= 1
        new_col = old_col + k
        if g_col[new_col] and i <= g_col[new_col][0] and g_col[new_col][-1] < i + k:
            new_white_line_nums += 1
        new_white_line_nums_col[i][old_col + 1] = new_white_line_nums

for i in range(n - k + 1):
    new_white_line_nums = 0
    for l in range(0, k):
        if g_row[l] and i <= g_row[l][0] and g_row[l][-1] < i + k:
            new_white_line_nums += 1
    # new_white_line_nums_row[0][i] = new_white_line_nums
    r = max(r, new_white_line_nums_col[0][i] + new_white_line_nums)

    for old_row in range(n - k):
        if g_row[old_row] and i <= g_row[old_row][0] and g_row[old_row][-1] < i + k:
            new_white_line_nums -= 1
        new_row = old_row + k
        if g_row[new_row] and i <= g_row[new_row][0] and g_row[new_row][-1] < i + k:
            new_white_line_nums += 1
        r = max(r, new_white_line_nums_col[old_row + 1][i] + new_white_line_nums)
        # new_white_line_nums_row[old_row + 1][i] = new_white_line_nums

# r = 0
# for i in range(n - k + 1):
#     for j in range(n - k + 1):
#         r = max(r, new_white_line_nums_col[i][j] + new_white_line_nums_row[i][j])

print(r + already_white_line_nums)


import sys
input = lambda: sys.stdin.readline().strip()

n, k = list(map(int, input().split()))
arr = []
for i in range(n):
    arr.append(list(input()))
extra = 0
res = []
for i in range(n-k+1):
    res.append([])
    for j in range(n-k+1):
        res[-1].append(0)

# ROWS

l = {}
r = {}
for i in range(n):
    for j in range(n):
        if arr[i][j]=='B': l[i] = j; break
    for j in range(n-1, -1, -1):
        if arr[i][j]=='B': r[i] = j; break
    else: l[i] = None; r[i] = None; extra+=1
for j in range(n-k+1):
    tmp = 0
    for i in range(k):
        if l[i] is not None and l[i]>=j and r[i]<=j+k-1:
            tmp+=1
    res[0][j]+=tmp
    for i in range(1, n-k+1):
        if l[i-1] is not None and l[i-1]>=j and r[i-1]<=j+k-1:
            tmp-=1
        if l[i+k-1] is not None and l[i+k-1]>=j and r[i+k-1]<=j+k-1:
            tmp+=1
        res[i][j]+=tmp

# COLUMNS

l = {}
r = {}
for j in range(n):
    for i in range(n):
        if arr[i][j]=='B': l[j] = i; break
    for i in range(n-1, -1, -1):
        if arr[i][j]=='B': r[j] = i; break
    else: l[j] = None; r[j] = None; extra+=1
for i in range(n-k+1):
    tmp = 0
    for j in range(k):
        if l[j] is not None and l[j]>=i and r[j]<=i+k-1:
            tmp+=1
    res[i][0]+=tmp
    for j in range(1, n-k+1):
        if l[j-1] is not None and l[j-1]>=i and r[j-1]<=i+k-1:
            tmp-=1
        if l[j+k-1] is not None and l[j+k-1]>=i and r[j+k-1]<=i+k-1:
            tmp+=1
        res[i][j]+=tmp

print(max(max(i) for i in res)+extra)


import sys
input = lambda: sys.stdin.readline().strip()
 
n, k = list(map(int, input().split()))
arr = []
for i in range(n):
    arr.append(list(input()))
extra = 0
res = []
for i in range(n-k+1):
    res.append([])
    for j in range(n-k+1):
        res[-1].append(0)
 
# ROWS
 
l = {}
r = {}
for i in range(n):
    for j in range(n):
        if arr[i][j]=='B': l[i] = j; break
    for j in range(n-1, -1, -1):
        if arr[i][j]=='B': r[i] = j; break
    else: l[i] = None; r[i] = None; extra+=1
for j in range(n-k+1):
    tmp = 0
    for i in range(k):
        if l[i] is not None and l[i]>=j and r[i]<=j+k-1:
            res[0][j]+=1
            tmp+=1
    for i in range(1, n-k+1):
        res[i][j]+=tmp
        if l[i-1] is not None and l[i-1]>=j and r[i-1]<=j+k-1:
            res[i][j]-=1
            tmp-=1
        if l[i+k-1] is not None and l[i+k-1]>=j and r[i+k-1]<=j+k-1:
            res[i][j]+=1
            tmp+=1
 
# COLUMNS
 
l = {}
r = {}
for j in range(n):
    for i in range(n):
        if arr[i][j]=='B': l[j] = i; break
    for i in range(n-1, -1, -1):
        if arr[i][j]=='B': r[j] = i; break
    else: l[j] = None; r[j] = None; extra+=1
for i in range(n-k+1):
    tmp = 0
    for j in range(k):
        if l[j] is not None and l[j]>=i and r[j]<=i+k-1:
            res[i][0]+=1
            tmp+=1
    for j in range(1, n-k+1):
        res[i][j]+=tmp
        if l[j-1] is not None and l[j-1]>=i and r[j-1]<=i+k-1:
            res[i][j]-=1
            tmp-=1
        if l[j+k-1] is not None and l[j+k-1]>=i and r[j+k-1]<=i+k-1:
            res[i][j]+=1
            tmp+=1
 
print(max(max(i) for i in res)+extra)


ac=[[0 for i in range(2010)]for j in range(2010)]
n,k=map(int,input().split())
v=[]
for i in range(n):
    v.append(input())
extra=0
##row
for i in range(n):
    L=n
    R=-1
    for j in range(n):
        if v[i][j]=='B':
            L=min(L,j)
            R=max(R,j)
    if L>R:
        extra += 1
    else:
        if R-L+1<=k:
            minx=max(0,i-k+1)
            maxx=i
            miny=max(0,R-k+1)
            maxy=L
            ac[minx][miny] += 1
            ac[maxx + 1][maxy + 1] += 1
            ac[maxx + 1][miny] -= 1
            ac[minx][maxy + 1] -= 1
for j in range(n):
    L=n
    R=-1
    for i in range(n):
        if v[i][j]=='B':
            L=min(L,i)
            R=max(R,i)
    if L>R:
        extra += 1
    else:
        if R-L+1<=k:
            minx=max(0,R-k+1)
            maxx=L
            miny=max(0,j-k+1)
            maxy=j
            ac[minx][miny] += 1
            ac[maxx + 1][maxy + 1] += 1
            ac[maxx + 1][miny] -= 1
            ac[minx][maxy + 1] -= 1
for i in range(n):
    for j in range(n):
        if i >0 :
            ac[i][j] += ac[i-1][j]
        if j > 0:
            ac[i][j] += ac[i][j-1]
        if i > 0 and j>0:
            ac[i][j] -= ac[i-1][j-1]
ans=0
for i in range(n-k+1):
    for j in range(n-k+1):
        ans=max(ans,ac[i][j])
print(ans+extra)

n,k=list(map(int,input().split()))
it=[[0]*n for i in range(n)]
t=[[-1,-1] for i in range(n)]
tt=[[-1,-1] for i in range(n)]
for i in range(n):
    s=input()
    c=-1
    cc=-1
    for j,ii in enumerate(s):
        if ii=="B":
            it[i][j]=1
            if c==-1:
                c=j
            cc=j
    t[i]=[c,cc]

for i in range(n):
    p=[it[j][i] for j in range(n)]
    c=-1
    cc=-1
    for j in range(n):
        if p[j]:
            if c==-1:
                c=j
            cc=j
    tt[i]=[c,cc]
row_max=[[0]*(n-k+1) for i in range(n-k+1)]
col_max=[[0]*(n-k+1) for i in range(n-k+1)]
for col in range(n-k+1):
    s=[0]*n
    co=0
    for i in range(k):
        if t[i]!=[-1,-1]:
            if t[i][0]>=col and t[i][0]<=col+k-1 and t[i][1]>=col and t[i][1]<=col+k-1:
                co+=1
                s[i]=1
    row_max[col][0]=co
    for row in range(1,n-k+1):
        if s[row-1]:
            co-=1
        i=row+k-1
        if t[i]!=[-1,-1]:
            if t[i][0]>=col and t[i][0]<=col+k-1 and t[i][1]>=col and t[i][1]<=col+k-1:
                co+=1
                s[i]=1
        row_max[col][row]=co
for row in range(n-k+1):
    s=[0]*n
    co=0
    for i in range(k):
        if tt[i]!=[-1,-1]:
            if tt[i][0]>=row and tt[i][0]<=row+k-1 and tt[i][1]>=row and tt[i][1]<=row+k-1:
                co+=1
                s[i]=1
    col_max[0][row]=co
    for col in range(1,n-k+1):
        if s[col-1]:
            co-=1
        i=col+k-1
        if tt[i]!=[-1,-1]:
            if tt[i][0]>=row and tt[i][0]<=row+k-1 and tt[i][1]>=row and tt[i][1]<=row+k-1:
                co+=1
                s[i]=1
        col_max[col][row]=co
ma=0
for i in range(n-k+1):
    for j in range(n-k+1):
        ma=max(ma,row_max[i][j]+col_max[i][j])
ma+=t.count([-1,-1])
ma+=tt.count([-1,-1])
print(ma)


    
            
    


import sys
from itertools import accumulate
N, K = map(int, input().split())
G = [[1 if s == 'B' else 0 for s in sys.stdin.readline().strip()] for _ in range(N)]

Ans = [[0]*(N+1) for _ in range(N+1)]
ans = 0

for i in range(N):
    g = G[i]
    if 1 not in g:
        ans += 1
        continue
    r = g.index(1)
    l = max(0, N - K - g[::-1].index(1))
    j = max(0, i-K+1)
    if l <= r:
        Ans[j][l] += 1
        Ans[j][r+1] -= 1
        Ans[i+1][l] -= 1
        Ans[i+1][r+1] += 1

G = list(map(list, zip(*G)))
Ans = list(map(list, zip(*Ans)))

for i in range(N):
    g = G[i]
    if 1 not in g:
        ans += 1
        continue
    r = g.index(1)
    l = max(0, N - K - g[::-1].index(1))
    j = max(0, i-K+1)
    if l <= r:
        Ans[j][l] += 1
        Ans[j][r+1] -= 1
        Ans[i+1][l] -= 1
        Ans[i+1][r+1] += 1

Ans = [list(accumulate(g))[::-1] for g in Ans]
Ans = list(map(list, zip(*Ans)))
Ans = [list(accumulate(g))[::-1] for g in Ans]

print(ans + max(max(g) for g in Ans))    

n, k = [int(i) for i in input().split()]
sz = n - k + 1
cnt = []
for i in range(sz):
    cnt.append([0]*(sz))
data = []
extra = 0
for i in range(n):
    data.append(input())
for r in range(n):
    row = data[r]
    li = row.find("B") 
    if li == -1:
        extra += 1
        continue
    ri = row.rfind("B")
    for i in range(max(ri - k+1,0), min(li+1, sz)):#??????????????
        for j in range(max(0, r+1-k), min(sz, r+1)):
            # print("row:",r, li, ri, j, i)
            cnt[j][i] += 1
# b = []
# b.rindex(1)


for c in range(n):
    row = "".join([data[i][c] for i in range(n)])
    li = row.find("B")
    if li == -1:
        extra += 1
        continue
    ri = row.rfind("B")
    for i in range(max(ri - k+1,0),  min(li+1, sz)):
        for j in range(max(0, c+1-k), min(sz, c+1)):
            # print("col:",c, li, ri,i,j)
            cnt[i][j] += 1

mx = 0
for i in range( sz):
    for j in range(sz):
        if cnt[i][j] > mx:
            mx = cnt[i][j]
print(mx+extra)

# print(cnt)


from math import *

MOD = int(1e9)+7

def nextInt():
    return int(input())

def nextInts():
    return list(map(int,input().split()))

def YN(x):
    return "YES" if x else "NO"

cum = None
n,k = 0,0

def addRect(x0,x1,y0,y1):
    nonlocal cum,n,k
    x0 = max(x0,0)+1
    x1 = min(x1,n-k)+1
    y0 = max(y0,0)+1
    y1 = min(y1,n-k)+1
    #print("HA",x0,x1,y0,y1)
    if x0 > x1 or y0 > y1:
        return
    #print("BEF",x0,x1,cum[1][1])
    cum[x0][y0] += 1
    #print("??",cum[1][1])
    cum[x1+1][y0] -= 1
    #print("??",x1+1,y0,cum[1][1],len(cum))
    cum[x0][y1+1] -= 1
    #print("??",cum[1][1])
    cum[x1+1][y1+1] += 1
    #print("??",cum[1][1])
    #print("AFT",cum[1][1])

def solve():
    nonlocal cum,n,k
    n,k = nextInts()
    L = []
    cum = [[0]*2005 for x in range(2005)]
    # print(cum[0])
    for i in range(n):
        L.append(input())
    for i in range(n):
        mn,mx = MOD,-MOD
        for j in range(n):
            if L[i][j] == 'B':
                mx = j
                if mn == MOD:
                    mn = j
        if mn == MOD:
            cum[1][1] += 1
            continue
        #print(i,mn,mx,mx-k+1,mn)
        addRect(i-k+1,i,mx-k+1,mn)
    for j in range(n):
        mn,mx = MOD,-MOD
        for i in range(n):
            if L[i][j] == 'B':
                mx = i
                if mn == MOD:
                    mn = i
        if mn == MOD:
            cum[1][1] += 1
            continue
        #print(j,mn,mx)
        addRect(mx-k+1,mn,j-k+1,j)
    ans = 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            cum[i][j] += cum[i][j-1]+cum[i-1][j]-cum[i-1][j-1]
            #print("HUH",i,j,cum[i][j])
            ans = max(ans,cum[i][j])
    return ans

print(solve())
# t = nextInt()
# for i in range(t):
#     print(YN(solve()))


[n, k] = [int(x) for x in input().split()]

# for every column
# find earliest and latest b
# create a list per column
# True -> earliest <= curr, latest <= curr+k
# False -> otherwise


# BWWW 100 110
# WBBW 010 020
# WBBW 010 011
# WWWB 001

# BWWW 1000 100
# WBBW 0110 121
# WBBW 0001 001
# WWWB

c_p1 = [[-1] * 2010 for x in range(2010)]
c_p2 = [[-1] * 2010 for x in range(2010)]

r_p1 = [[-1] * 2010 for x in range(2010)]
r_p2 = [[-1] * 2010 for x in range(2010)]

cells = []
for i in range(n):

    cells.append(input())

bonus = 0

for y in range(n):
    earliest = -1
    latest = -1
    for x in range(n):
        if cells[y][x] == "B":
            earliest = x
            break
    for x in range(n):
        if cells[y][n - x - 1] == "B":
            latest = n - x - 1
            break

    if earliest == -1:
        bonus += 1
    for x in range(n - k + 1):
        r_p1[y][x] = int(earliest >= x and x + k - 1 >= latest)

for x in range(n - k + 1):
    sum = 0
    for y in range(n):
        sum += r_p1[y][x]
        if y - k >= 0:
            sum -= r_p1[y - k][x]

        if y - k + 1 >= 0:
            r_p2[y - k + 1][x] = sum


for x in range(n):
    earliest = -1
    latest = -1
    for y in range(n):
        if cells[y][x] == "B":
            earliest = y
            break
    for y in range(n):
        if cells[n - y - 1][x] == "B":
            latest = n - y - 1
            break
    if earliest == -1:
        bonus += 1
    for y in range(n - k + 1):
        c_p1[y][x] = int(earliest >= y and y + k - 1 >= latest)

for y in range(n - k + 1):
    sum = 0
    for x in range(n):
        sum += c_p1[y][x]
        if x - k >= 0:
            sum -= c_p1[y][x - k]

        if x - k + 1 >= 0:
            c_p2[y][x - k + 1] = sum

# print(r_p2[0][:3])
# print(r_p2[1][:3])
# print(r_p2[2][:3])

# print(c_p2[0][:3])
# print(c_p2[1][:3])
# print(c_p2[2][:3])

ans = 0
for y in range(n - k + 1):
    for x in range(n - k + 1):
        ans = max(ans, c_p2[y][x] + r_p2[y][x])
# print(bonus)
print(ans + bonus)


n, k = map(int ,input().split())

c_p1 = [[-1] * 2001 for x in range(2001)]
c_p2 = [[-1] * 2001 for x in range(2001)]
 
r_p1 = [[-1] * 2001 for x in range(2001)]
r_p2 = [[-1] * 2001 for x in range(2001)]
 
cells = []
for i in range(n):
 
    cells.append(input())
 
bonus = 0
 
for y in range(n):
    earliest = -1
    latest = -1
    for x in range(n):
        if cells[y][x] == "B":
            earliest = x
            break
    for x in range(n):
        if cells[y][n - x - 1] == "B":
            latest = n - x - 1
            break
 
    if earliest == -1:
        bonus += 1
    for x in range(n - k + 1):
        r_p1[y][x] = int(earliest >= x and x + k - 1 >= latest)
 
for x in range(n - k + 1):
    sum = 0
    for y in range(n):
        sum += r_p1[y][x]
        if y - k >= 0:
            sum -= r_p1[y - k][x]
 
        if y - k + 1 >= 0:
            r_p2[y - k + 1][x] = sum
 
 
for x in range(n):
    earliest = -1
    latest = -1
    for y in range(n):
        if cells[y][x] == "B":
            earliest = y
            break
    for y in range(n):
        if cells[n - y - 1][x] == "B":
            latest = n - y - 1
            break
    if earliest == -1:
        bonus += 1
    for y in range(n - k + 1):
        c_p1[y][x] = int(earliest >= y and y + k - 1 >= latest)
 
for y in range(n - k + 1):
    sum = 0
    for x in range(n):
        sum += c_p1[y][x]
        if x - k >= 0:
            sum -= c_p1[y][x - k]
 
        if x - k + 1 >= 0:
            c_p2[y][x - k + 1] = sum
 
ans = 0
for y in range(n - k + 1):
    for x in range(n - k + 1):
        ans = max(ans, c_p2[y][x] + r_p2[y][x])

print(ans + bonus)

import sys
import math as mt
#input=sys.stdin.buffer.readline  
#t=int(input())
t=1
for __ in range(t):
    n,k=list(map(int,input().split()))
    arr=[]
    lr={}
    d={}
    ans=0
    for i  in range(n):
        arr.append(input())
        lr[i]=[]
        for j in range(n):
            if arr[i][j]=='B':
                lr[i].append(j)
                break
        for j in range(n-1,-1,-1):
            if arr[i][j]=='B':
                lr[i].append(j)
                break
        if len(lr[i])==0:
            lr[i].append(-1)
            lr[i].append(-1)
            d[i]=1
            ans+=1
        else:
            d[i]=0
    lr1={}
    d1={}
    for j in range(n):
        lr1[j]=[]
        for i in range(n):
            if arr[i][j]=='B':
                lr1[j].append(i)
                break
        for i in range(n-1,-1,-1):
            if arr[i][j]=='B':
                lr1[j].append(i)
                break
        if len(lr1[j])==0:
            d1[j]=1
            ans+=1
            lr1[j].append(-1)
            lr1[j].append(-1)

        else:
            d1[j]=0
    #print(arr,lr)        
    a={}
    
    i1=0
    fans1=[[0 for j in range(n)] for i in range(n)]
    fans2=[[0 for j in range(n)] for i in range(n)]
    for i1 in range(n-k+1):
        a[i1]=[]
        ans1=0
        #print(33,i1,i1+k-1)
        for i in range(k):
            if d[i]==0:
                if k+i1>lr[i][1] and i1<=lr[i][0]:
                    ans1+=1   
        #print(111,ans1)
            
        #a[i1].append(ans1)
        fans1[0][i1]=ans1
        for i in range(n-k):
            if d[i]==0 and k+i1>lr[i][1] and i1<=lr[i][0] :
                ans1-=1
            if d[i+k]==0 and lr[i+k][1]<k+i1 and i1<=lr[i+k][0]:
                ans1+=1
            fans1[i+1][i1]=ans1    
            #a[i1].append(ans1)
    b={}
    #print(arr,lr1,d1)
    for i1 in range(n-k+1):
        b[i1]=[]
        ans1=0
        #print(33,i1,i1+k-1)
        for i in range(k):
            if d1[i]==0:
                if k+i1>lr1[i][1] and i1<=lr1[i][0]:
                    ans1+=1   
        #print(111,ans1)
        fans2[i1][0]=ans1    
        b[i1].append(ans1)
        for i in range(n-k):
            if d1[i]==0 and k+i1>lr1[i][1] and i1<=lr1[i][0] :
                ans1-=1
            if d1[i+k]==0 and lr1[i+k][1]<k+i1 and i1<=lr1[i+k][0]:
                ans1+=1
            fans2[i1][i+1]=ans1    
            b[i1].append(ans1)
            
        #print(fans)
    maxi=0    
    for i in range(n):
        for j in range(n):
            maxi=max(fans1[i][j]+fans2[i][j],maxi)
            
    #print(fans1)
    #print(fans2)
    print(maxi+ans)        
    #n=int(input())
    #h=list(map(int,input().split()))


n,k = list(map(int,input().split()))
mat = []
for i in range(n):
	mat.append(list(input()))
prefr = [[0 for i in range(n)] for j in range(n)]
prefc = [[0 for i in range(n)] for j in range(n)]
done = 0
for i in range(n):
	for j in range(n):
		if j==0 and mat[i][j]=="B":
			prefr[i][j] = 1
		else:
			prefr[i][j] = prefr[i][j-1]
			if mat[i][j]=="B":
				prefr[i][j] += 1
		if i==0 and mat[i][j]=="B":
			prefc[i][j] = 1
		else:
			prefc[i][j] = prefc[i-1][j]
			if mat[i][j]=="B":
				prefc[i][j] += 1
for i in range(n):
	if prefc[-1][i]==0:
		done += 1
	if prefr[i][-1]==0:
		done += 1
dr,dc = [[0 for i in range(n)] for j in range(n)],[[0 for i in range(n)] for j in range(n)]
for j in range(n-k+1):
	count = []
	s = 0
	for i in range(k):
		if j==0:
			if prefr[i][-1]-prefr[i][j+k-1]==0 and prefr[i][-1]!=0:
				count.append(1)
				s += 1
			else:
				count.append(0)
		else:
			if prefr[i][j-1] + (prefr[i][-1]-prefr[i][j+k-1]) == 0 and prefr[i][-1]!=0:
				count.append(1)
				s += 1
			else:
				count.append(0)
	dr[0][j] = s
	# print (count,s)
	for i in range(1,n-k+1):
		if j==0:
			if prefr[i+k-1][-1]-prefr[i+k-1][j+k-1]==0 and prefr[i+k-1][-1]!=0:
				count.append(1)
				s += 1
			else:
				count.append(0)
		else:
			if prefr[i+k-1][j-1] + (prefr[i+k-1][-1]-prefr[i+k-1][j+k-1]) == 0 and prefr[i+k-1][-1]!=0:
				count.append(1)
				s += 1
			else:
				count.append(0)
		# print (i,j,s)
		if count[i-1]==1 and prefr[i-1][-1]!=0:
			s -= 1 
		dr[i][j] = s
# print (dr)
for i in range(n-k+1):
	count = []
	s = 0
	for j in range(k):
		if i==0:
			if prefc[-1][j]-prefc[i+k-1][j]==0 and prefc[-1][j]!=0:
				count.append(1)
				s += 1
			else:
				count.append(0)
		else:
			if prefc[i-1][j] + (prefc[-1][j]-prefc[i+k-1][j]) == 0 and prefc[-1][j]!=0:
				count.append(1)
				s += 1
			else:
				count.append(0)
	dc[i][0] = s
	# print (count,s)
	for j in range(1,n-k+1):
		if i==0:
			if prefc[-1][j+k-1]-prefc[i+k-1][j+k-1]==0 and prefc[-1][j+k-1]!=0:
				count.append(1)
				s += 1
			else:
				count.append(0)
		else:
			if prefc[i-1][j+k-1] + (prefc[-1][j+k-1]-prefc[i+k-1][j+k-1]) == 0 and prefc[-1][j+k-1]!=0:
				count.append(1)
				s += 1
			else:
				count.append(0)
		# print (i,j,s)
		if count[j-1]==1 and prefc[-1][j-1]!=0:
			s -= 1 
		dc[i][j] = s
# print (dc)
ans = 0
for i in range(n):
	for j in range(n):
		ans = max(ans,dr[i][j]+dc[i][j])
print(ans+done)