Maximum Square Side Length Under Sum Threshold

Given an m x n matrix \(mat\) of integers and an integer \(threshold\), find the maximum side-length \(L\) of any square sub-matrix such that the sum of its elements is less than or equal to \(threshold\). If no such square exists, output 0.

You can use prefix sum (cumulative sum) technique to calculate the sum of any square sub-matrix efficiently. Specifically, if we define the prefix sum matrix \(P\) as:

\[ P[i][j] = \sum_{r=0}^{i-1}\sum_{c=0}^{j-1} mat[r][c] \]

then the sum of a square with top-left corner \((i, j)\) and side-length \(L\) can be computed as:

\[ S = P[i+L][j+L] - P[i][j+L] - P[i+L][j] + P[i][j] \]

Your task is to implement a solution that reads input from standard input (stdin) and prints the result to standard output (stdout).

inputFormat

The input is given via stdin in the following format:

• The first line contains two space-separated integers \(m\) and \(n\) which denote the number of rows and columns of the matrix, respectively.
• The next \(m\) lines each contain \(n\) space-separated integers representing the elements of the matrix.
• The final line contains a single integer \(threshold\).

outputFormat

The output should be printed to stdout and consist of a single integer: the maximum side-length of a square sub-matrix with a sum less than or equal to \(threshold\). If no such square exists, output 0.

## sample

3 7
1 1 3 2 4 3 2
1 1 3 2 4 3 2
1 1 3 2 4 3 2
4

2