Maximum Beauty Sum in a Grid

You are given an N x N grid of integers and an integer K. Your task is to find the maximum sum of any contiguous K x K subgrid. In other words, you should slide a K x K window over the grid (only within valid boundaries) and compute the sum of the elements inside the window. The answer is the largest sum among all these windows.

Note: The grid might contain negative numbers.

The problem can be stated mathematically using the following formula:

$$\text{max sum} = \max_{1 \leq i \leq N-K+1 \atop 1 \leq j \leq N-K+1} \left\{ \sum_{a=0}^{K-1} \sum_{b=0}^{K-1} grid_{i+a,j+b} \right\} $$

inputFormat

The input consists of multiple datasets. Each dataset is formatted as follows:

• The first line contains two integers: N and K.
• The next N lines each contain N integers, representing the grid.

The datasets are given consecutively, and the end of input is indicated by a line containing "0 0".

outputFormat

For each dataset, output a single line containing the maximum beauty sum of any K x K subgrid.

## sample

4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3 1
-1 -2 -3
-4 -5 -6
-7 -8 -9
0 0

54
-1

</p>