페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10428

역도 20s 1024MB

문제

당신은 정해진 역도 훈련 프로그램을 따르고 있다. 이 훈련은 순서대로 수행해야 하는 일련의 운동(exercise)들로 이루어져 있다. 각 운동은 기계에 특정한 구성의 무게추를 올려야 한다.

무게추의 종류는 서로 다른 \mathbf{W}가지가 있다. 예를 들어 어떤 운동은 A 타입 무게추 3개와 B 타입 무게추 1개가 필요하고, 다음 운동은 A, C, D 타입 무게추가 각각 2개씩 필요할 수 있다.

Weightlifting example.

무게추들은 기계 위에 스택(stack) 형태로 쌓인다. 형식적으로, 한 번의 연산으로 임의의 타입의 무게추 하나를 스택의 맨 위에 올리거나, 현재 스택의 맨 위에 있는 무게추 하나를 제거할 수 있다.

각 운동에 필요한 무게추들을 스택에 올리는 순서는 당신이 마음대로 정할 수 있다. 따라서 위 예시에서 첫 번째 운동에서 B 타입 무게추를 맨 아래에 두면, 두 번째 운동을 위해 모든 무게추를 다 빼고 다시 올려야 한다. 반면 B 타입 무게추를 아래에서 세 번째 위치에 두면, A 타입 무게추 2개를 스택의 아래쪽에 그대로 남겨 다음 운동의 무게추 구성에 포함시킬 수 있어 시간을 절약할 수 있다.

각 운동마다 각 타입의 무게추가 몇 개 필요한지가 주어질 때, 모든 운동을 수행하기 위해 필요한 연산 횟수의 최소를 구하라. 운동은 주어진 순서대로 완료해야 한다. 기계의 스택은 처음에 비어 있고, 모든 운동을 끝냈을 때도 스택을 비워 둬야 한다.


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 정수 두 개 \mathbf{E}, \mathbf{W}가 주어진 한 줄로 시작한다. 이는 각각 운동의 개수와 무게추 종류의 개수이다. 무게추 종류는 1부터 \mathbf{W}까지 번호가 매겨져 있다. 그 다음 \mathbf{E}줄이 이어진다. 이 중 i번째 줄에는 \mathbf{W}개의 정수 \mathbf{X_{i,1}}, \mathbf{X_{i,2}}, \dots, \mathbf{X_{i,W}}가 주어진다. 이는 i번째 운동에 타입 j의 무게추가 정확히 \mathbf{X_{i,j}}개 필요하다는 뜻이다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 모든 운동을 수행하기 위해 필요한 기계 스택 연산 횟수의 최소값이다.


예제 

3
3 1
1
2
1
2 3
1 2 1
2 1 2
3 3
3 1 1
3 3 3
2 3 3
Case #1: 4
Case #2: 12
Case #3: 20
샘플 케이스 #1에서는 무게 종류가 하나뿐이다. 첫 번째 운동은 1개, 두 번째는 2개, 세 번째는 1개가 필요하다. 다음과 같이 4번의 연산으로 운동을 완료할 수 있다: 무게 하나를 스택에 올린다. 첫 번째 운동을 한다. 무게 하나를 스택에 올린다. 두 번째 운동을 한다. 스택 맨 위의 무게 하나를 제거한다. 세 번째 운동을 한다. 스택 맨 위의 무게 하나를 제거한다. 이제 스택이 비게 된다. 샘플 케이스 #2에서 12번의 연산으로 운동을 완료하는 한 가지 방법은 다음과 같다: 타입 2의 무게를 하나 올린다. 타입 3의 무게를 하나 올린다. 타입 1의 무게를 하나 올린다. 타입 2의 무게를 하나 올린다. 이제 스택에는 아래에서 위로 2, 3, 1, 2가 있다. 첫 번째 운동을 한다. 스택 맨 위의 타입 2 무게를 제거한다. 타입 3의 무게를 하나 올린다. 타입 1의 무게를 하나 올린다. 이제 스택에는 아래에서 위로 2, 3, 1, 3, 1이 있다. 두 번째 운동을 한다. 스택 맨 위의 타입 1 무게를 제거한다. 스택 맨 위의 타입 3 무게를 제거한다. 스택 맨 위의 타입 1 무게를 제거한다. 스택 맨 위의 타입 3 무게를 제거한다. 스택 맨 위의 타입 2 무게를 제거한다. 이제 스택이 비게 된다.

출처

GCJ 2022r1a C

로그인해야 코드를 작성할 수 있어요.