시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 13 9 6 60.000%

문제

민호는 N개의 주식 상품을 가지고 있다.  그리고 모든 상품들은 연간 주가가 시간순으로 K개 기록이 되어 있다.

민호는 각 상품들의 주가를 시간순으로 잇는 선그래프들을 그려 주가 변동을 하눈에 보고 싶어졌다.

한 개의 상품마다 한 개의 차트를 사용하기에는 공간을 너무 많이 차지하기 때문에 민호는 최소한의 차트를 이용해 모든 주식의 변동 그래프를 그리고 싶었다.

하지만 선분이 겹치거나 교차해 버리면 주식의 변동 그래프를 보기 힘들기 때문에 한 차트 그려지는 그래프들은 서로 겹치지 않게 하고 싶다.

이런 조건을 지켜 모든 주식상품들의 그래프를 그릴 때 최소 몇 개의 차트가 필요한지 알아보자.

입력

첫 번째 줄에 테스트 케이스 T가 들어온다.

각 테스트케이스의 첫 번째 줄에는 N, K ( 1 ≤ N ≤ 100, 1 ≤ K ≤ 25 ) 가 공백을 구분으로 주어진다. 이는 각각 민호가 그림으로 정리하고 싶어하는 주식의 개수와 각 주식 상품들마다 기록이 되어있는 주가들의 개수이다.

두 번째 줄부터 N개의 줄에 걸쳐 Pij (0 ≤ Pij ≤ 1000000 ) 가 주어진다. Pij는 i번째 상품이 j번 시간일때 주가를 의미한다.

출력

모든 주식 상품을 주가변동을 선 그래프로 그렸을 때 겹치거나 교차하지 않게 그릴 수 있는 최소한의 차트의 개수를 출력한다.

예제 입력 1

3
3 4
1 2 3 4
2 3 4 6
6 5 4 3
3 3
5 5 5
4 4 6
4 5 4
5 2
1 1
2 2
5 4
4 4
4 1

예제 출력 1

2
3
2

출처

  • 문제의 오타를 찾은 사람: jh05013