접시

Dr. Patel에게는 접시 더미가 N개 있다. 각 더미에는 접시가 K개 있다. 각 접시에는 그 접시가 얼마나 아름다워 보이는지를 나타내는 양의 아름다움 값이 있다.

Dr. Patel은 오늘 저녁 식사에 사용할 접시를 정확히 P개 가져가려고 한다. 어떤 더미에서 접시 하나를 가져가려면, 그 더미에서 그 접시 위에 있는 모든 접시도 함께 가져가야 한다.

Dr. Patel이 고른 접시들의 아름다움 값 총합이 최대가 되도록 P개의 접시를 고르는 것을 도와주자.

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ K ≤ 30. 1 ≤ P ≤ N * K. 아름다움 값은 1 이상 100 이하이다.

테스트 세트 1

1 ≤ N ≤ 3.

테스트 세트 2

1 ≤ N ≤ 50.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 N, K, P가 포함된 한 줄로 시작한다. 그다음 N개의 줄이 주어진다. i번째 줄에는 K개의 정수가 주어지며, 각 접시 더미의 아름다움 값을 위에서 아래 순서로 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작한다), y은 Dr. Patel이 고를 수 있는 접시들의 아름다움 값 총합의 최댓값이다.

예제 케이스 #1에서 Dr. Patel은 P = 5개의 접시를 골라야 한다.

• 첫 번째 더미 (10 + 10 + 100 = 120)에서 맨 위의 접시 3개를 고를 수 있다.

• 두 번째 더미 (80 + 50 = 130)에서 맨 위의 접시 2개를 고를 수 있다.

아름다움 값의 총합은 250이다.

예제 케이스 #2에서 Dr. Patel은 P = 3개의 접시를 골라야 한다.

• 첫 번째 더미 (80 + 80 = 160)에서 맨 위의 접시 2개를 고를 수 있다.

• 두 번째 더미에서는 접시를 하나도 고르지 않을 수 있다.

• 세 번째 더미에서 맨 위의 접시 하나를 고를 수 있다(20).

아름다움 값의 총합은 180이다.

참고: 이전 대회들과 달리 Kick Start 2020에서는 모든 테스트 세트가 결과가 공개되는 테스트 세트이므로, 제출 즉시 결과를 확인할 수 있다.