Maximum Sub-Grid with Sum Constraint

You are given a 2D grid (matrix) of integers and an integer threshold \(T\). Your task is to find the largest possible size \(k\) (i.e. the side-length of a square sub-grid) such that there exists at least one \(k \times k\) sub-grid in which the sum of all its elements is less than or equal to \(T\). If no such sub-grid exists, output 0.

More formally, let \(A\) be an \(n \times m\) matrix and let a square sub-grid with top-left corner at \((i,j)\) and size \(k\) be defined as the set of cells \(\{A_{p,q}\}\) with \(i \le p \le i+k-1\) and \(j \le q \le j+k-1\). You need to determine the maximum \(k\) such that there exists an \(i,j\) for which

[ \sum_{p=i}^{i+k-1}\sum_{q=j}^{j+k-1} A_{p,q} \le T. ]

If no valid sub-grid exists, the answer is 0.

inputFormat

The input is given in the following format over stdin:

n m
A[0][0] A[0][1] ... A[0][m-1]
A[1][0] A[1][1] ... A[1][m-1]
...
A[n-1][0] A[n-1][1] ... A[n-1][m-1]
T

Where the first line contains two space-separated integers \(n\) and \(m\) representing the number of rows and columns respectively. The next \(n\) lines each contain \(m\) space-separated integers representing the matrix. The last line contains the integer threshold \(T\).

outputFormat

Output a single integer to stdout: the maximum sub-grid size \(k\) for which there exists a \(k \times k\) sub-grid whose total sum does not exceed \(T\). If no valid sub-grid exists, output 0.

1 1
1
1

1