Maximum Sum Subgrid with K Elements

You are given a grid with N rows and M columns, filled with integers. Your task is to find the maximum sum obtainable from a contiguous rectangular subgrid that contains exactly K elements.

A subgrid is defined as a contiguous block of cells in the grid. In other words, you are to choose two indices (r1, c1) and (r2, c2) with 1 ≤ r1 ≤ r2 ≤ N and 1 ≤ c1 ≤ c2 ≤ M such that the number of elements in the subgrid (i.e. (r2 − r1 + 1) * (c2 − c1 + 1)) is exactly K. The sum of the subgrid is the total of its elements. You must output the maximum such sum among all valid subgrids.

Note: It is guaranteed that there is at least one way to choose a subgrid with exactly K elements for the given input.

Constraints: The input grid size and K are such that a valid subgrid exists, and multiple test cases may appear.

inputFormat

The first line contains three integers N, M, and K separated by spaces. This is followed by N lines, each containing M integers separated by spaces, representing the grid.

outputFormat

Output a single integer representing the maximum sum of a subgrid that contains exactly K elements.## sample

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

28