Maximum Sum Submatrix

Given an n x n matrix and an integer k, your task is to find the maximum sum of all possible k x k submatrices within the matrix. A submatrix is a contiguous block of cells within the original matrix.

You may use an efficient approach using prefix sums. The prefix sum prefix[i][j] for a matrix is defined as:

\( prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] \)

Then, the sum of any k x k submatrix with bottom-right corner at \( (i, j) \) can be computed as:

\( currentSum = prefix[i][j] - prefix[i-k][j] - prefix[i][j-k] + prefix[i-k][j-k] \)

Calculate the maximum currentSum over all valid positions.

inputFormat

The first line of input contains two space-separated integers, n and k.

Then follow n lines, each line containing n integers representing the rows of the matrix.

\( 1 \leq k \leq n \leq 10^3 \) and the matrix elements can be any integer (possibly negative).

outputFormat

Output a single integer which is the maximum sum of a k x k submatrix within the given matrix.

## sample

4 2
1 5 3 2
8 2 4 1
5 9 6 3
2 6 7 8

28