성적 상승 대작전

시간 제한8초메모리 제한512 MB

요약

N장의 일별 시트 순서를 바꿔 점수가 끝까지 감소하지 않는 과목의 최대 개수를 구합니다. N은 1000 이하, M은 40 이하입니다.

난이도: 보통10점 중 7점
유형: 그래프, 비트 연산, 완전 탐색
정답자: 아직 제출이 없습니다

문제

타로군은 N일 동안 진행된 공부 합숙에 참가했다. 이 합숙에서는 매일 M개 과목의 시험을 치렀고, 합숙이 끝나면 모든 시험의 점수가 적힌 성적표를 나누어 주었다. 성적표는 N장의 종이로 이루어져 있고, i번째 장에는 i일째 M개 과목의 과목명과 점수만 인쇄되어 있다.

성적표에 날짜가 적혀 있지 않다는 것을 알아챈 타로군은 어머니께 성적표를 드리기 전에 손을 대기로 했다. 성적표 장의 순서를 바꾼 뒤 1쪽부터 차례로 쪽 번호를 적어 책자로 만든 것이다. 타로군의 목표는 이 “거짓 성적표”에서 점수가 쪽 번호에 대해 광의 단조 증가하는 과목의 개수를 최대로 만드는 것이다.

광의 단조 증가란 1 ≤ i < N인 모든 i에 대해 i+1번째 장에 적힌 점수가 i번째 장에 적힌 점수 이상이라는 뜻이다.

입력

입력은 최대 50개의 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식으로 주어진다.

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

첫 줄에 합숙 일수 N과 과목 수 M이 주어진다. N은 1 이상 103 이하의 정수이고, M은 1 이상 40 이하의 정수이다.

이어지는 N줄에 타로군의 점수가 주어진다. 각 줄은 M개의 정수로 이루어지며, aij는 타로군의 i일째 과목 j의 점수이다. aij는 0 이상 103 이하의 정수이다.

입력의 끝은 0 0 두 개로 이루어진 줄로 표시된다.

출력

각 데이터셋에 대해, 쪽 번호에 대해 점수가 광의 단조 증가하는 과목 수의 최댓값을 한 줄에 출력하라.

예제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

예상 출력