// test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
  

int Calculate(int R,int K,int N, int g[])
{
	int nMax = 0; 		
	if (N == 1)
	{
		nMax = g[0] * R;
	}
	else
	{
		int i = 0;
		int nFirst = 0,nLast = N-1;
		for (int j=0;j<R;j++)
		{
			int nTemp = 0;
			for (i= nFirst; i % N != nLast ; i++)
			{
				nTemp += g[i % N];
				if (nTemp > K)
				{
					nTemp -= g[i % N];
					nFirst = i;
					nLast = i % N - 1;
					break;	
				}
			} 
			if (i % N == nLast)
			{
				nFirst = i;
				nLast = i% N - 1;
			}
			nMax +=nTemp;
		}
	}
	return nMax;
}
int main(int argc, char* argv[])
{ 

	const int MAX = 256;
	char cLines[MAX+1] = {0};
	FILE *fIn = fopen("in.txt","r");
	FILE *fOut = fopen("out.txt","w");
	if (fIn == NULL || fOut == NULL) 
		return -1;

	int R,K,N;
	int *g;
	if (fgets(cLines,MAX,fIn) != NULL)
	{
		int nCount = atoi(cLines);
		for (int i=0;i<nCount;i++)
		{
			memset(cLines,0,MAX+1);
			fgets(cLines,MAX,fIn);
			char *temp;

			temp = cLines; 
			R = atoi(temp);
			
			temp = strchr(temp,' ');
			if (temp == NULL)
				break;
			temp++;
			K = atoi(temp);

			temp = strchr(temp,' ');
			if (temp == NULL)
				break;
			temp++;
			N = atoi(temp);
		
			g = new int[N];
			fgets(cLines,MAX,fIn);
			temp = cLines;
			for (int j=0;j<N;j++)
			{				
				*(g+j) = atoi(temp);
				temp = strchr(temp,' ');
				if (temp == NULL)
					break;
				temp++;
			}
			_snprintf(cLines,MAX,"Case #%d:%d\r\n",i+1,Calculate(R,K,N,g)); 
			delete []g;
			fputs(cLines,fOut);
		}
	} 
	fclose(fIn);
	fclose(fOut);
	return 0;
}