Maximum Sum of Subgrid

You are given an \(n \times n\) grid of integers and an integer \(k\). Your task is to compute the maximum sum of any \(k \times k\) subgrid within the given grid.

To solve this problem efficiently, you may want to use a prefix sum array. The prefix sum \(P[i][j]\) of the grid is defined as:

[ P[i][j] = \sum_{a=1}^{i} \sum_{b=1}^{j} grid[a][b] ]

Then, the sum of a subgrid with the upper-left corner \((i - k + 1, j - k + 1)\) and bottom-right corner \((i, j)\) can be computed as:

[ S = P[i][j] - P[i - k][j] - P[i][j - k] + P[i - k][j - k] ]

Output the maximum such sum among all \(k \times k\) subgrids.

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space.

The next \(n\) lines each contain \(n\) space-separated integers representing the grid.

Input Format:

n k
row1_element1 row1_element2 ... row1_elementn
row2_element1 row2_element2 ... row2_elementn
...
rown_element1 rown_element2 ... rown_elementn

outputFormat

Output a single integer which is the maximum sum of a \(k \times k\) subgrid.

Output Format:

max_sum

## sample

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

54