시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 512 MB3000.000%

문제

受験生の太郎君は N 日間の勉強合宿に参加した. この合宿では毎日 M 科目のテストを行い, 合宿の終了後にはすべてのテストの点数が書かれた成績表が配られる. 成績表は N 枚の紙からなっており,i 枚目の紙には i 日目の全 M 科目のテストの科目名と点数のみが印刷されている.

成績表に日付が書かれていないことに気付いた太郎君は,お母さんに成績表を渡す前に細工を加えることにした. 成績表の紙の順番を並べ替え,さらに1枚目から順番にページ番号を書き込んで冊子にすることによって「偽りの成績表」を作ったのだ. 太郎君の目的は,「偽りの成績表」でテストの点数がページ番号に対して広義単調増加している科目の個数を最大化することである.

太郎君が「偽りの成績表」を作るとき,テストの点数がページ番号に対して広義単調増加である科目の個数の最大値を求めよ.

ただし,N 日間のテストの点数がページ番号に対して広義単調増加であるとは 1 ≤ i < N に対して i+1 枚目に記載されている点数が i 枚目に記載されている点数以上であることを意味する.

입력

入力は 50 個以下のデータセットからなる. 各データセットは次の形式で表される.

N M
a11 ... a1M
...
aN1 ... aNM

1行目には,勉強合宿の日数 N と科目数 M が与えられる.N は 1 以上 103 以下の整数で,M は 1 以上 40 以下の整数である.

続く N 行には太郎君の点数が与えられる.各行は M 個の整数からなっており aij は太郎君の i 日目の科目 j の点数であり,aij は 0 以上 103 以下の整数である.

入力の終わりは,2 つのゼロからなる行で表される.

출력

各データセットについて,テストの点数がページ番号に対して広義単調増加である科目の個数の最大値を 1 行に出力せよ.

예제 입력 1

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

예제 출력 1

2
3
1
9