Maximum Sum Subgrid

You are given a matrix of size \(N \times M\) containing non-negative integers. Your task is to find the maximum sum of any contiguous subgrid of size \(K \times K\) within the matrix.

A subgrid is defined by \(K\) consecutive rows and \(K\) consecutive columns. To solve this efficiently, consider using a prefix sum (cumulative sum) approach which allows you to calculate the sum of any subgrid in constant time once the prefix sum matrix has been computed.

Example:

Input:
4 5 3
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
Output:
126

</p>

In the above matrix, the \(3 \times 3\) subgrid with the maximum sum is:

[ \begin{bmatrix} 7 & 8 & 9\ 12 & 13 & 14\ 17 & 18 & 19 \end{bmatrix} ]

whose sum is (7 + 8 + 9 + 12 + 13 + 14 + 17 + 18 + 19 = 126).

inputFormat

The first line of input contains three space-separated integers \(N\), \(M\), and \(K\) representing the number of rows, the number of columns, and the subgrid size respectively.

The next \(N\) lines each contain \(M\) space-separated integers, representing the rows of the matrix.

outputFormat

Output a single integer which is the maximum sum of any \(K \times K\) subgrid within the given matrix.

## sample

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

126