역도

당신은 정해진 역도 훈련을 따르고 있다. 훈련은 순서대로 수행해야 하는 일련의 운동으로 구성된다. 각 운동을 하려면 특정 구성의 원판을 기계에 올려야 한다.

서로 다른 원판 종류가 $\mathbf{W}$개 있다. 예를 들어 어떤 운동에는 A형 원판 $3$개와 B형 원판 $1$개가 필요할 수 있고, 다음 운동에는 A형, C형, D형 원판이 각각 $2$개 필요할 수 있다.

원판은 기계에 스택 형태로 올린다. 엄밀히 말해 한 번의 연산으로 임의의 종류인 새 원판 하나를 스택의 맨 위에 추가하거나, 현재 스택의 맨 위에 있는 원판을 제거할 수 있다.

각 운동에 필요한 원판은 어떤 순서로든 기계의 스택에 올릴 수 있다. 따라서 위 예제의 첫 번째 운동에서 B형 원판을 맨 아래에 놓으면, 두 번째 운동에 필요한 원판을 올리기 전에 모든 원판을 빼야 한다. 반면 B형 원판을 아래에서 세 번째에 놓으면 A형 원판 두 개를 스택 맨 아래에 그대로 두어 다음 운동의 구성에 포함할 수 있으므로 시간을 어느 정도 절약할 수 있다.

각 운동에 필요한 종류별 원판의 개수가 주어질 때, 모든 운동을 수행하는 데 필요한 최소 연산 횟수를 구한다. 운동은 주어진 순서대로 완료해야 한다. 기계의 스택은 처음에 비어 있으며, 모든 운동을 마친 뒤에도 비어 있게 해야 한다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{X_{i,1}} + \mathbf{X_{i,2}} + \dots + \mathbf{X_{i,W}}$. (각 운동에는 적어도 하나의 원판이 필요하다.)

테스트 세트 1 (Visible Verdict)

$1 \le \mathbf{E} \le 10$. $1 \le \mathbf{W} \le 3$. 모든 $i, j$에 대해 $0 \le \mathbf{X_{i,j}} \le 3$.

테스트 세트 2 (Hidden Verdict)

$1 \le \mathbf{E} \le 100$. $1 \le \mathbf{W} \le 100$. 모든 $i, j$에 대해 $0 \le \mathbf{X_{i,j}} \le 100$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 운동의 수와 원판 종류의 수를 나타내는 $2$개의 정수 $\mathbf{E}$와 $\mathbf{W}$가 포함된 줄로 시작한다. 원판 종류에는 $1$부터 $\mathbf{W}$까지의 번호가 매겨져 있다. 이어서 $\mathbf{E}$개의 줄이 주어진다. 이 줄들 중 $i$번째 줄에는 $i$번째 운동에 $j$형 원판이 정확히 $\mathbf{X_{i,j}}$개 필요함을 나타내는 $\mathbf{W}$개의 정수 $\mathbf{X_{i,1}}, \mathbf{X_{i,2}}, \dots, \mathbf{X_{i,W}}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 운동을 차례로 수행하는 데 필요한 기계 스택 연산의 최소 횟수이다.

예제 케이스 #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$형 원판 하나를 제거한다. 이제 스택이 빈다.