Largest Increasing Submatrix

Finding the longest contiguous increasing subsequence of a list of numbers is a classic programming contest problem. You solve the same problem here, with one change: the numbers are given as a two-dimensional matrix, and the longest sequence is embedded in a submatrix of the original matrix.

Here is the precise definition. The linearization of a two-dimensional matrix is the sequence formed by joining its rows one after another, from the first row to the last. A submatrix is a rectangular region of a matrix whose sides are parallel to the sides of the matrix. The size of a submatrix is its number of elements. Write a program that, given a matrix of integers, finds the largest submatrix whose linearization is an increasing sequence.

The figure below shows some examples of maximum-size submatrices that contain increasing sequences. A matrix can contain more than one submatrix with a sequence of maximum length. An increasing sequence cannot contain repeated elements: 22, 31, 33 is increasing, but 22, 31, 31, 33 is not.

For the three matrices in the figure, the answers are 4, 3, and 9.

The input contains several test cases. The first line of each test case contains two integers $N$ and $M$, the dimensions of the matrix ($1 \le N, M \le 600$). Each of the next $N$ lines contains $M$ integers separated by single spaces, the elements of the matrix. The element $X_{i,j}$ is the $j$-th integer on the $i$-th of these lines ($-10^6 \le X_{i,j} \le 10^6$).

The end of the input is marked by a line that contains only two zeros separated by a space.

For each test case, print one line with the number of elements in the largest submatrix whose linearization is an increasing sequence.