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: HARD
Tags: Amortized analysis

Implementation

Complete search

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Amortized analysis

Complete search

Starter code:

Solutions:
import sys
import math as mt
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
	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
		for i in range(k):
			if d[i] == 0:
				if k + i1 > lr[i][1] and i1 <= lr[i][0]:
					ans1 += 1
		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
	b = {}
	for i1 in range(n - k + 1):
		b[i1] = []
		ans1 = 0
		for i in range(k):
			if d1[i] == 0:
				if k + i1 > lr1[i][1] and i1 <= lr1[i][0]:
					ans1 += 1
		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)
	maxi = 0
	for i in range(n):
		for j in range(n):
			maxi = max(fans1[i][j] + fans2[i][j], maxi)
	print(maxi + ans)


from math import *
MOD = int(1000000000.0) + 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
	if x0 > x1 or y0 > y1:
		return
	cum[x0][y0] += 1
	cum[x1 + 1][y0] -= 1
	cum[x0][y1 + 1] -= 1
	cum[x1 + 1][y1 + 1] += 1

def solve():
	nonlocal cum, n, k
	(n, k) = nextInts()
	L = []
	cum = [[0] * 2005 for x in range(2005)]
	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
		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
		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]
			ans = max(ans, cum[i][j])
	return ans
print(solve())


[n, k] = [int(x) for x in input().split()]
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
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)


(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
input = lambda : sys.stdin.readline().strip()
(n, k) = 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)
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
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)


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(ans)

def __starting_point():
	main()
__starting_point()


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) = 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)
		elif 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
	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)
		elif 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)
		if count[i - 1] == 1 and prefr[i - 1][-1] != 0:
			s -= 1
		dr[i][j] = s
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)
		elif 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
	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)
		elif 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)
		if count[j - 1] == 1 and prefc[-1][j - 1] != 0:
			s -= 1
		dc[i][j] = s
ans = 0
for i in range(n):
	for j in range(n):
		ans = max(ans, dr[i][j] + dc[i][j])
print(ans + done)


import sys
import math, bisect
sys.setrecursionlimit(10 ** 5)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict

def I():
	return int(sys.stdin.readline())

def neo():
	return map(int, sys.stdin.readline().split())

def Neo():
	return list(map(int, sys.stdin.readline().split()))
(N, K) = neo()
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) = 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
	if not g_col[i]:
		already_white_line_nums += 1
r = 0
new_white_line_nums_col = [[[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
	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)
print(r + already_white_line_nums)


import re
from collections import deque
from functools import reduce
from heapq import *
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep
from sys import stdin

def rline() -> str:
	return stdin.readline().rstrip()

def fmatr(matrix, lnsep: str=linesep, fieldsep: str=' ') -> str:
	return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))

def fbool(boolval: int) -> str:
	return ['No', 'Yes'][boolval]

def gcd(a: int, b: int) -> int:
	(a, b) = (max([a, b]), min([a, b]))
	if b == 0:
		return a
	return gcd(b, a % b)

def solve() -> None:
	(n, k) = map(int, rline().split())
	s = [rline() for i in range(n)]
	(tb, bb, lb, rb) = [[-1] * n for i in range(4)]
	for cell in range(n ** 2):
		r = cell // n
		c = cell % n
		if s[r][c] == 'B':
			bb[c] = r
			if tb[c] == -1:
				tb[c] = r
		if s[r][c] == 'B':
			rb[r] = c
			if lb[r] == -1:
				lb[r] = c
	ans = 0
	df = tb.count(-1) + lb.count(-1)
	(l4r, r4l) = [[{} for i in range(n)] for j in range(2)]
	for y in range(k):
		(l, r) = (lb[y], rb[y])
		if l == -1:
			continue
		l4r[r][l] = 1 + l4r[r].get(l, 0)
		r4l[l][r] = 1 + r4l[l].get(r, 0)
	for top in range(n - k + 1):
		subans = df
		btm = top + k
		for y in range(top, btm):
			if 0 <= lb[y] <= rb[y] < k:
				subans += 1
		for x in range(k):
			if top <= tb[x] <= bb[x] < btm:
				subans += 1
		ans = max([ans, subans])
		for rm in range(n - k):
			ad = rm + k
			if top <= tb[rm] <= bb[rm] < btm:
				subans -= 1
			if top <= tb[ad] <= bb[ad] < btm:
				subans += 1
			subans -= sum(map(lambda r: r4l[rm][r] if r < ad else 0, r4l[rm].keys()))
			subans += sum(map(lambda l: l4r[ad][l] if l > rm else 0, l4r[ad].keys()))
			ans = max([ans, subans])
		if rb[top] != -1:
			l4r[rb[top]][lb[top]] -= 1
			if l4r[rb[top]][lb[top]] == 0:
				l4r[rb[top]].pop(lb[top])
			r4l[lb[top]][rb[top]] -= 1
			if r4l[lb[top]][rb[top]] == 0:
				r4l[lb[top]].pop(rb[top])
		if btm < n and rb[btm] != -1:
			l4r[rb[btm]][lb[btm]] = 1 + l4r[rb[btm]].get(lb[btm], 0)
			r4l[lb[btm]][rb[btm]] = 1 + r4l[lb[btm]].get(rb[btm], 0)
	print(ans)
solve()


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

def main():
	(n, k) = 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)
main()


(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 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))))


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(' '))
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)


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
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
	elif 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
	elif 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)


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) = 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))))


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, k) = map(int, input().split())
m = n
l = []
ans = 0
for i in range(n):
	l.append(input())
whi = [0 for i in range(n)]
ran = [[-1 for j in range(2)] for i in range(n)]
for i in range(n):
	st = 2001
	end = -1
	for j in range(m):
		if l[i][j] == 'B':
			st = min(st, j)
			end = max(end, j)
	if end == -1:
		whi[i] = 1
	else:
		ran[i][0] = st
		ran[i][1] = end
ans1 = sum(whi)
a = [[0 for i in range(m)] for j in range(n)]
for j in range(m):
	cur = 0
	last = [0] * n
	for i in range(k):
		if whi[i] == 1:
			continue
		if ran[i][0] >= j and ran[i][1] <= j + k - 1:
			cur += 1
			last[i] = 1
	a[0][j] = cur
	for i in range(k, n):
		if last[i - k] == 1:
			cur -= 1
		if whi[i] == 1:
			continue
		if ran[i][0] >= j and ran[i][1] <= j + k - 1:
			cur += 1
			last[i] = 1
		a[i - k + 1][j] = cur
whi = [0 for i in range(n)]
ran = [[-1 for j in range(2)] for i in range(n)]
for i in range(n):
	st = 2001
	end = -1
	for j in range(m):
		if l[j][i] == 'B':
			st = min(st, j)
			end = max(end, j)
	if end == -1:
		whi[i] = 1
	else:
		ran[i][0] = st
		ran[i][1] = end
b = [[0 for i in range(m)] for j in range(n)]
for j in range(n):
	cur = 0
	last = [0] * n
	for i in range(k):
		if whi[i] == 1:
			continue
		if ran[i][0] >= j and ran[i][1] <= j + k - 1:
			cur += 1
			last[i] = 1
	b[j][0] = cur
	for i in range(k, m):
		if last[i - k] == 1:
			cur -= 1
		if whi[i] == 1:
			continue
		if ran[i][0] >= j and ran[i][1] <= j + k - 1:
			cur += 1
			last[i] = 1
		b[j][i - k + 1] = cur
for i in range(n):
	for j in range(m):
		ans = max(ans, a[i][j] + b[i][j])
print(ans + sum(whi) + ans1)


(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
		elif 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
		elif 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)


import sys
input = sys.stdin.readline
(n, k) = 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)


import sys
from sys import stdin
(n, k) = map(int, stdin.readline().split())
S = [stdin.readline()[:-1] for i in range(n)]
orians = 0
lis = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	minj = float('inf')
	maxj = float('-inf')
	for j in range(n):
		if S[i][j] == 'B':
			minj = min(minj, j)
			maxj = max(maxj, j)
	if minj == float('inf'):
		orians += 1
		continue
	if maxj - minj + 1 <= k:
		x1 = max(0, i - k + 1)
		x2 = i + 1
		y1 = max(0, maxj - k + 1)
		y2 = minj + 1
		lis[x1][y1] += 1
		lis[x1][y2] -= 1
		lis[x2][y1] -= 1
		lis[x2][y2] += 1
for j in range(n):
	mini = float('inf')
	maxi = float('-inf')
	for i in range(n):
		if S[i][j] == 'B':
			mini = min(mini, i)
			maxi = max(maxi, i)
	if mini == float('inf'):
		orians += 1
		continue
	if maxi - mini + 1 <= k:
		x1 = max(0, maxi - k + 1)
		x2 = mini + 1
		y1 = max(0, j - k + 1)
		y2 = j + 1
		lis[x1][y1] += 1
		lis[x1][y2] -= 1
		lis[x2][y1] -= 1
		lis[x2][y2] += 1
ans = 0
for i in range(n):
	for j in range(n - 1):
		lis[i][j + 1] += lis[i][j]
for i in range(n - 1):
	for j in range(n):
		lis[i + 1][j] += lis[i][j]
for i in range(n):
	for j in range(n):
		ans = max(ans, lis[i][j])
print(ans + orians)


(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)):
			cnt[j][i] += 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)):
			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)


from collections import deque

def final(ans, arr):
	queue = deque()
	count = 0
	for i in range(n):
		count = 0
		queue = deque()
		for j in range(n - 1, -1, -1):
			if queue and queue[0] - j + 1 > k:
				queue.popleft()
				count = max(count - 1, 0)
			if i >= arr[j][0] and i <= arr[j][1]:
				count += 1
				queue.append(j)
			ans[i][j] = count
	return ans

def check(arr, i, j, k):
	global count
	for l in range(i, j, k):
		if arr[l] == 'B':
			return l
	count += 1
	return -1
(n, k) = map(int, input().split())
arr_1 = []
arr_2 = []
for i in range(n):
	arr_1.append(input())
st = ''
for i in range(n):
	st = ''
	for j in range(n):
		st += arr_1[j][i]
	arr_2.append(st)
count = 0
hori_arr = [[0, 0] for i in range(n)]
verti_arr = [[0, 0] for i in range(n)]
for i in range(n):
	hori_arr[i][0] = check(arr_1[i], 0, n, 1)
	verti_arr[i][0] = check(arr_2[i], 0, n, 1)
	hori_arr[i][1] = check(arr_1[i], n - 1, -1, -1)
	verti_arr[i][1] = check(arr_2[i], n - 1, -1, -1)
count //= 2
temp = 0
for i in range(n):
	if hori_arr[i][1] - k + 1 <= hori_arr[i][0] and hori_arr[i][0] >= 0:
		temp = hori_arr[i][0]
		hori_arr[i][0] = max(0, hori_arr[i][1] - k + 1)
		hori_arr[i][1] = temp
	else:
		hori_arr[i][0] = hori_arr[i][1] = -1
	if verti_arr[i][1] - k + 1 <= verti_arr[i][0] and verti_arr[i][0] >= 0:
		temp = verti_arr[i][0]
		verti_arr[i][0] = max(0, verti_arr[i][1] - k + 1)
		verti_arr[i][1] = temp
	else:
		verti_arr[i][0] = verti_arr[i][1] = -1
ans1 = [[0 for i in range(n)] for j in range(n)]
ans2 = [[0 for i in range(n)] for j in range(n)]
x = final(ans1, verti_arr)
y = final(ans2, hori_arr)
maxi = 0
for i in range(n):
	for j in range(n):
		maxi = max(x[i][j] + y[j][i], maxi)
print(maxi + count)


(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 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)))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[n - 1]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[0]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
(n, k) = map(int, input().split())
m = n
l = []
ans = 0
for i in range(n):
	l.append(input())
whi = [0 for i in range(n)]
ran = [[-1 for j in range(2)] for i in range(n)]
for i in range(n):
	st = 2001
	end = -1
	for j in range(m):
		if l[i][j] == 'B':
			st = min(st, j)
			end = max(end, j)
	if end == -1:
		whi[i] = 1
	else:
		ran[i][0] = st
		ran[i][1] = end
ans1 = sum(whi)
a = [[0 for i in range(m)] for j in range(n)]
for j in range(m):
	cur = 0
	last = [0] * n
	for i in range(k):
		if whi[i] == 1:
			continue
		if ran[i][0] >= j and ran[i][1] <= j + k - 1:
			cur += 1
			last[i] = 1
	a[0][j] = cur
	for i in range(k, n):
		if last[i - k] == 1:
			cur -= 1
		if whi[i] == 1:
			continue
		if ran[i][0] >= j and ran[i][1] <= j + k - 1:
			cur += 1
			last[i] = 1
		a[i - k + 1][j] = cur
whi = [0 for i in range(n)]
ran = [[-1 for j in range(2)] for i in range(n)]
for i in range(n):
	st = 2001
	end = -1
	for j in range(m):
		if l[j][i] == 'B':
			st = min(st, j)
			end = max(end, j)
	if end == -1:
		whi[i] = 1
	else:
		ran[i][0] = st
		ran[i][1] = end
b = [[0 for i in range(m)] for j in range(n)]
for j in range(n):
	cur = 0
	last = [0] * n
	for i in range(k):
		if whi[i] == 1:
			continue
		if ran[i][0] >= j and ran[i][1] <= j + k - 1:
			cur += 1
			last[i] = 1
	b[j][0] = cur
	for i in range(k, m):
		if last[i - k] == 1:
			cur -= 1
		if whi[i] == 1:
			continue
		if ran[i][0] >= j and ran[i][1] <= j + k - 1:
			cur += 1
			last[i] = 1
		b[j][i - k + 1] = cur
for i in range(n):
	for j in range(m):
		ans = max(ans, a[i][j] + b[i][j])
print(ans + sum(whi) + ans1)