가장 큰 증가 부분 행렬

수열에서 가장 긴 연속 증가 부분 수열을 찾는 문제는 프로그래밍 대회의 고전이다. 이 문제도 같은 것을 구하지만 조금 바꾸었다. 수는 2차원 행렬로 주어지고, 가장 긴 증가 수열은 원래 행렬의 부분 행렬 안에 들어 있다.

문제를 정확히 정의하자. 2차원 행렬의 선형화는 첫 행부터 마지막 행까지 행을 차례로 이어 붙인 수열이다. 부분 행렬은 행렬에서 변이 행렬의 변과 평행한 직사각형 영역이다. 부분 행렬의 크기는 그 안에 있는 원소의 개수이다. 정수 행렬이 주어질 때, 선형화하면 증가 수열이 되는 부분 행렬 중 가장 큰 것을 찾는 프로그램을 작성하시오.

아래 그림은 증가 수열을 담은 최대 크기 부분 행렬의 예이다. 한 행렬 안에 최대 길이 수열을 담은 부분 행렬이 여러 개 있을 수도 있다. 증가 수열에는 같은 원소가 반복될 수 없다. 22, 31, 33은 증가 수열이지만 22, 31, 31, 33은 증가 수열이 아니다.

그림의 세 행렬에서 답은 차례로 4, 3, 9이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 행렬의 크기를 나타내는 두 정수 $N$과 $M$이 주어진다 ($1 \le N, M \le 600$). 다음 $N$개의 줄에는 각각 $M$개의 정수가 공백 하나로 구분되어 주어지며, 이 수들이 행렬의 원소이다. 행렬의 원소 $X_{i,j}$는 입력의 $i$번째 줄의 $j$번째 정수이다 ($-10^6 \le X_{i,j} \le 10^6$).

입력의 끝은 공백 하나로 구분된 두 개의 0만 있는 줄로 나타낸다.

각 테스트 케이스마다 한 줄에, 선형화하면 증가 수열이 되는 가장 큰 부분 행렬의 원소 개수를 출력한다.