Maximum Subgrid Sum Under Limit

You are given an H × W matrix of integers and an integer K. Your task is to find the largest possible sum of any subgrid (i.e., a contiguous rectangular part of the matrix) such that this sum does not exceed K.

A subgrid is defined by its top-left corner (r1, c1) and bottom-right corner (r2, c2) (using 0-based indexing), and its sum can be computed using the formula:

\(S = \sum_{i=r1}^{r2} \sum_{j=c1}^{c2} matrix[i][j]\)

Your goal is to maximize S while ensuring that \(S \leq K\). It is guaranteed that if no valid subgrid exists that satisfies the condition (i.e. all subgrid sums are greater than K), the answer is 0.

Note: Use efficient approaches such as prefix sums to compute subgrid sums quickly.

inputFormat

The input consists of multiple test cases. Each test case begins with three integers H, W, and K separated by spaces, where H and W denote the number of rows and columns of the matrix respectively, and K is the upper limit for the subgrid sum.

This is followed by H lines, each containing W space-separated integers representing the rows of the matrix.

The input terminates with a line containing 0 0 0, which should not be processed.

outputFormat

For each test case, output a single line containing the maximum subgrid sum that does not exceed K.

## sample

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

7

</p>