Under construction

Still being built. Things may change

White Lines

Interview

Time limit1.5sMemory limit256 MB

Summary
Given an n by n grid of black and white cells, paint one k by k square white to maximize the number of fully white rows and columns.
Level

Medium5 of 10

Topics
Prefix sum, Matrix, Implementation
Solved
No attempts yet

Problem

Gildong has bought a famous painting software cfpaint. The working screen of cfpaint is a square of nn rows and nn columns of cells. Rows are numbered 1 to nn from top to bottom, and columns are numbered 1 to nn from left to right. The cell at row rr and column cc is written (r,c)(r,c). Each cell is either black or white.

The eraser tool has an integer size kk (1≤k≤n1\le k\le n). To use it, Gildong clicks a cell (i,j)(i,j) with 1≤i,j≤n−k+11\le i,j\le n-k+1. Every cell (i′,j′)(i',j') with i≤i′≤i+k−1i\le i'\le i+k-1 and j≤j′≤j+k−1j\le j'\le j+k-1 becomes white. In other words, the square of side kk with top left corner (i,j)(i,j) is painted white.

A white line is a row or column with no black cells.

Gildong has used cfpaint for a while, so some cells (possibly none or all) are black now. Find the maximum number of white lines after using the eraser exactly once.

Input

The first line has two integers nn and kk (1≤k≤n≤20001\le k\le n\le 2000), the number of rows and columns and the eraser size. The next nn lines each contain nn characters without spaces. The jj-th character of the ii-th line is the cell (i,j)(i,j): 'B' for black, 'W' for white.

Output

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

Hint

In the first example, Gildong can click cell (2,2)(2,2). The screen then becomes:

BWWW
WWWW
WWWW
WWWB

There are four white lines: rows 2 and 3, and columns 2 and 3.

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

In the third example, clicking cell (3,2)(3,2) makes both column 2 and row 5 white lines.

Examples5

  1. Example 1

    Input
    4 2
    BWWW
    WBBW
    WBBW
    WWWB
    
    Expected output
    4
    
  2. Example 2

    Input
    3 1
    BWB
    WWB
    BWB
    
    Expected output
    2
    
  3. Example 3

    Input
    5 3
    BWBBB
    BWBBB
    BBBBB
    BBBBB
    WBBBW
    
    Expected output
    2
    
  4. Example 4

    Input
    2 2
    BW
    WB
    
    Expected output
    4
    
  5. Example 5

    Input
    2 1
    WW
    WW
    
    Expected output
    4