Maximize Land Value for the Capital

In a virtual world, leader Xiao Z believes that the three factors of timing, location, and manpower are all essential. Choosing the position of the capital is therefore extremely important. The capital occupies a square of size \( C \times C \). Given a grid representing the value of the land in each cell, your task is to find a \( C \times C \) submatrix where the total land value is maximized.

Note: The grid may contain negative values, so it is possible that the maximum sum is negative.

inputFormat

The first line contains three integers \( N \), \( M \), and \( C \) representing the number of rows, the number of columns in the grid, and the side length of the capital respectively. \( (1 \leq C \leq N, M) \)

Each of the following \( N \) lines contains \( M \) integers, representing the value of the land in that cell.

outputFormat

Output a single integer: the maximum total land value that can be obtained by any \( C \times C \) submatrix.

sample

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

28