1200_D. White Lines
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 ≤ k ≤ n). To use the eraser, Gildong needs to click on a cell (i, j) where 1 ≤ i, j ≤ n - k + 1. When a cell (i, j) is clicked, all of the cells (i', j') where i ≤ i' ≤ i + k - 1 and j ≤ j' ≤ 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 ≤ k ≤ n ≤ 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).
```python
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)
```