Maximum Sub-grid Sum

You are given an N x N grid of integers and an integer k. Your task is to compute the maximum sum of any contiguous k x k sub-grid within the given grid.

If k > N, then no valid sub-grid exists and you should output 0.

The sum of a sub-grid is defined as the sum of all integers contained in that sub-grid. A sub-grid is contiguous if it is formed by selecting k consecutive rows and k consecutive columns from the grid.

You may find it useful to utilize prefix sum techniques for efficient summation of sub-grids. The summation for any sub-grid with top-left corner at (i, j) in LaTeX can be expressed as:

\[ S = P(i+k, j+k) - P(i, j+k) - P(i+k, j) + P(i, j) \] where P is the prefix sum matrix.

inputFormat

The first line of input contains two integers N and k (separated by a space), representing the size of the grid and the size of the sub-grid, respectively.

Then follow N lines, each containing N integers. Each line represents a row of the grid, and the integers are separated by spaces.

outputFormat

Output a single integer, representing the maximum sum of any k x k sub-grid. If k > N, output 0.

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

54