HDU6444

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e4+7;

bool vis[N];
int Q[N*3];
ll A[N*3];
int a[N];

int main(){
    int T;r(T);
    for(int cas=1;cas<=T;++cas){
        int n,m,k;
        ll s,ans=0;
        r(n),r(s),r(m),r(k);
        memset(vis,0,n);
        for(int i=0;i<n;++i){
            r(a[i]);
        }
        for(int i=0;i<n;++i){
            if(vis[i])continue;
            int len=0;
            ll sum=0;
            for(int j=i;!vis[j];j=(j+k)%n){
                vis[j]=1;
                A[len++]=a[j];
                sum+=a[j];
            }
            int x=m/len,y=m%len;
            ll ret=0;
            if(x>0){
                --x;
                y+=len;
                for(int i=0;i<len;++i){
                    A[i+2*len]=A[i+len]=A[i];
                }
                len*=3;
            }
            else {
                for(int i=0;i<len;++i){
                    A[i+len]=A[i];
                }
                len*=2;
            }
            for(int i=1;i<len;++i){
                A[i]+=A[i-1];
            }
            int tail=0,head=1;
            for(int i=0;i<len;++i){
                while(head<=tail&&A[Q[tail]]>=A[i])tail--;
                while(head<=tail&&Q[head]<i-y)head++;
                Q[++tail]=i;
                ret=max(ret,A[i]-A[Q[head]]);
            }
            ret+=max(0ll,sum*x);
            ans=max(ans,ret);
        }
        printf("Case #%d: %lld\n",cas,max(0ll,s-ans));
    }
}
/*
1
5 10 3 1
1 -1 3 2 -5

*/