접시

Patel 박사에게는 접시 더미 N개가 있다. 각 더미에는 접시 K개가 쌓여 있다. 각 접시에는 그 접시가 얼마나 아름다운지 나타내는 양의 아름다움 값이 있다.

Patel 박사는 오늘 저녁 식사에 쓸 접시를 정확히 P개 가져가려고 한다. 어떤 더미에서 접시를 하나 가져가려면, 그 더미에서 그 접시 위에 있는 접시도 모두 가져가야 한다.

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

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

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

• 1 ≤ T ≤ 100.
• 1 ≤ K ≤ 30.
• 1 ≤ P ≤ N * K.
• 아름다움 값은 1 이상 100 이하이다.

예제 1에서 Patel 박사는 P = 5개의 접시를 골라야 한다:

• 첫 번째 더미에서 위쪽 3개의 접시를 고를 수 있다 (10 + 10 + 100 = 120).
• 두 번째 더미에서 위쪽 2개의 접시를 고를 수 있다 (80 + 50 = 130).

아름다움 값의 합은 모두 250이다.

예제 2에서 Patel 박사는 P = 3개의 접시를 골라야 한다:

• 첫 번째 더미에서 위쪽 2개의 접시를 고를 수 있다 (80 + 80 = 160).
• 두 번째 더미에서는 아무 접시도 고를 수 없다.
• 세 번째 더미에서 맨 위 접시 하나를 고를 수 있다 (20).

아름다움 값의 합은 모두 180이다.