E. Uniform Square Tiling
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A family has recently moved into a new apartment. One of the square walls in their living room is adorned with square tiles made of gold and silver. These tiles are arranged in a seemingly random fashion, without any discernible pattern. However, the family desires the wall to be uniform.

Unfortunately, shortly after moving in, they do not have the funds to purchase new tiles or hire professionals experienced in working with such valuable materials to re-tile the entire wall. As a temporary solution, the head of the family decided to cover a large portion of the wall with paintings, cabinets, and other wall decor. Nonetheless, they do not wish to conceal the entire wall. Instead, they opted to leave a square section of the wall visible, upon which they plan to place vases with flowers. To achieve a visually pleasing appearance, they will need to remove some tiles and replace them with tiles of the other material so that the visible square is completely uniformly tiled.

Now, they need to determine which section of the wall to keep visible. Naturally, they would like to select the section that requires the minimal number of tile replacements. The family needs to first ascertain how many tiles will need to be replaced in order to facilitate this process.

Input

The first line of the input file contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 1\,000$$$, $$$1 \leq k \leq 100$$$, $$$k \leq n$$$), separated by a space. Here, $$$n$$$ represents the dimension of the wall in tiles, and $$$k$$$ represents the dimension of the desired visible square in tiles.

The next $$$n$$$ lines contain $$$n$$$ characters each, representing the layout of the tiles on the wall. The character "G" denotes a gold tile, while the character "S" indicates a silver tile.

Output

Output a single integer $$$m$$$, which denotes the minimum number of tile replacements required to form a $$$k \times k$$$ square on the wall consisting entirely of identical tiles.

Examples
Input
3 2
GGG
SSG
GGG
Output
1
Input
5 3
GGGGG
SSSSS
GGGGG
SSSSS
GGGGG
Output
3