Largest Rectangle with Minimum Height Constraint

You are given an n x n grid of integers and an integer threshold h. Your task is to determine the area of the largest rectangle (submatrix) in which every cell has a value greater than or equal to h.

The problem can be approached by converting the original grid into a binary grid, where each cell is set to 1 if its value is at least h, and 0 otherwise. After this conversion, the problem reduces to finding the largest rectangular area composed entirely of 1's.

A typical method for solving this problem is to use a histogram-based approach. For each row, treat it as the base of a histogram where the height of each bar is the number of consecutive 1's above (including the current row). Then, apply a stack-based algorithm to compute the maximum rectangle area for that histogram.

Mathematically, if we denote the area of a rectangle as \( \text{area} = width \times height \), you need to find:

\[ \max_{\text{submatrix}} \{ (i_2 - i_1 + 1) \times (j_2 - j_1 + 1) \mid \min_{i_1 \leq i \leq i_2,\ j_1 \leq j \leq j_2} grid[i][j] \geq h \} \]

Solve the problem by reading input from stdin and output the result to stdout.

inputFormat

The first line of input contains two integers n and h, where n is the size of the grid. Each of the next n lines contains n space-separated integers representing the grid.

outputFormat

Output a single integer representing the area of the largest rectangle in the grid such that every cell in the rectangle has a value greater than or equal to h.## sample

4 3
3 3 3 3
3 2 2 3
3 2 2 3
3 3 3 3

4