Maximum Weight Square Subgrid

Given a binary grid of size n × m (where each cell is either 0 or 1), find the square subgrid that has the maximum weight. The weight of a square subgrid is defined as the square of its side length, i.e., \(side^2\). In other words, if the maximum square subgrid consisting entirely of 1's has side length k, then its weight is \(k^2\). If no square subgrid of 1's exists, output 0.

Your task is to compute this maximum weight using an efficient dynamic programming approach. The algorithm should work for any given grid dimensions.

Example:

Input:
3 3
1 0 1
0 1 0
1 0 1
Output:
1

inputFormat

The input is read from stdin and has the following format:

The first line contains two integers n and m separated by a space, representing the number of rows and columns of the grid respectively.

This is followed by n lines, each containing m space-separated integers (each being either 0 or 1) that represent the grid.

outputFormat

The output should be written to stdout. It consists of a single integer: the maximum weight (i.e., area) of any square subgrid of 1's found in the grid. If there is no such square, print 0.## sample

3 3
1 0 1
0 1 0
1 0 1

1