레이팅 미적용Plate Shipping Company는 이름 그대로 접시만 파는 인터넷 소매업체이다. 이들은 수많은 제조사의, 우주에서 가장 다양한 접시를 취급한다는 데 자부심을 갖고 있다. 최근 비용 분석에서 회사는 배송을 위한 접시 포장에 큰돈을 쓰고 있음을 발견했다. 그 이유 중 하나는 접시를 배송 컨테이너에 넣기 전에 쌓아야 하기 때문이다. 그리고 이것이 예상보다 시간이 오래 걸리는 모양이다. 당신이 도울 수 있을지도 모른다. 한 배송분의 접시는 여러 제조사의 접시로 이루어진다. 각 제조사의 접시는 쌓인 채로 오는데, 즉 크기 순서대로(가장 작은 것이 맨 위, 가장 큰 것이 맨 아래) 정렬된 하나의 더미로 온다. 이런 더미를 올바르게 정렬된 더미라고 부르자. 이 접시들을 모두 배송하려면 이들을 다시 올바르게 정렬된 하나의 더미로 합쳐야 한다. 제조사별 더미들을 하나의 더미로 합칠 때 두 종류의 연산이 허용된다.
-
분할(Split): 한 더미의 위쪽 일부를 들어 옆에 놓아 새 더미를 만들어, 더미 하나를 두 더미로 나눌 수 있다.
-
결합(Join): 한 더미를 다른 더미 위에 올려 두 더미를 합칠 수 있다. 이는 위 더미의 맨 아래 접시가 아래 더미의 맨 위 접시보다 크지 않을 때, 즉 합친 더미가 올바르게 정렬될 때에만 허용된다. 어떤 더미의 일부를 다른 더미 위에 곧바로 올릴 수는 없다는 점에 유의하라. 먼저 분할한 뒤, 분할된 부분을 다른 더미와 결합해야 한다. 더미들의 모음이 주어질 때, 이들을 하나의 더미로 만드는 최소 연산 횟수를 구해야 한다. 다음 예는 샘플 입력에 해당하며, 두 더미를 다섯 번의 연산으로 하나의 더미로 만드는 방법을 보여 준다.
각 테스트 케이스는 배송을 위해 합쳐야 하는 더미의 수를 나타내는 정수 \(n\) (\(1 \le n \le 50\)) 하나가 있는 줄로 시작한다. 이어서 \(n\)개의 줄이 각각 더미 하나를 설명한다. 각 줄은 더미의 높이 \(h\) (\(1 \le h \le 50\))로 시작한다. 이 수 뒤에는 접시의 지름을 위에서 아래 순서로 나타내는 \(h\)개의 양의 정수가 이어진다. 모든 지름은 최대 10 000이다. 이 수들은 감소하지 않는(n\(on-de\)creasing) 순서로 주어진다.
각 테스트 케이스마다 케이스 번호와, 주어진 더미들을 하나의 더미로 합치기 위해 수행해야 하는 연산(분할과 결합)의 최소 횟수를 출력한다.
2
3 1 2 4
2 3 5
3
4 1 1 1 1
4 1 1 1 1
4 1 1 1 1
Case 1: 5
Case 2: 2