Maximum Rectangular Area in Terrace Grid

You are given a grid of terraces with dimensions \(M \times N\). Each cell in the grid has a water capacity. You are also given a total amount of water \(W\). Your task is to determine the maximum area of a contiguous rectangular subgrid (i.e. a set of consecutive rows and columns) such that the sum of the capacities in that subgrid is less than or equal to \(W\). In other words, find the largest rectangle (by number of cells) in the grid for which the total water required does not exceed \(W\).

Input: The first line contains three integers: \(M\), \(N\) and \(W\). It is followed by \(M\) lines, each with \(N\) integers representing the capacities of each cell in the terrace grid.

Output: Output a single integer, which is the maximum rectangular area that can be completely filled with the available water.

Examples:

• Input:
  3 3 30
  1 2 3
  4 5 6
  7 8 9
  Output: 6
• Input:
  2 2 10
  4 5
  6 7
  Output: 2
• Input:
  3 3 1
  10 20 30
  40 50 60
  70 80 90
  Output: 0

inputFormat

The input consists of multiple lines:

1. The first line contains three space-separated integers \(M\), \(N\), and \(W\), where \(M\) and \(N\) denote the number of rows and columns of the grid respectively, and \(W\) is the total available water.
2. The next \(M\) lines each contain \(N\) space-separated integers representing the water capacities of the terraces.

outputFormat

Output a single integer representing the maximum rectangular area (number of cells) where the sum of terrace capacities does not exceed \(W\).

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

6