Largest Sub-Grid

Given a square integer matrix grid and an integer maxSum, return the largest k such that there exists a k × k contiguous sub-grid whose sum is ≤ maxSum. If no 1 × 1 sub-grid qualifies, return 0.

Constraints

• grid is an n × n matrix, 1 ≤ n ≤ 500
• 0 ≤ grid[i][j] ≤ 10⁵
• 1 ≤ maxSum ≤ 10¹⁰

Example 1

Input:

grid = [[2, 2, 2], [3, 3, 3], [4, 4, 4]]
maxSum = 4

Output:

0

Explanation: Every 1 x 1 square in the last row sums to 4, but no larger square stays within the limit. Under the prompt's example, the maximum valid size is 0.