题意：

有n个数形成一个环，问走最多走m次，每次k步，可以从任意位置开始，问得到的最大价值为多少。

思路：

对于一个环，固定步数下是有循环节的。不同循环节内的节点各不相同，根据裴蜀定理可得每个循环节的长度为n/gcd(n, k)。

所以暴力求出所有循环节。对于每个循环节，可以走k步，可知圈数num和圈数外的c，所以有两种情况：

1. 走num圈，并且对于不够整个循环节的c，求这个循环节的长度不超过c的最大子段和。

2. 有时候走num-1圈，然后取循环节的长度不超过len的最大子段和会更优。

   如这组数据：

   1
   5 100 12 1
   -10 1 2 3 5

   ans：1 2 3 5 -10 1 2 3 5

   max = 12

这里要注意有负环的情况，这时候圈数就不用走了，直接走其他的就行（见注释处）。

求不超过某个长度的最大子段和用单调队列优化的dp就可以了。

代码：

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
ll a[10010];
bool vis[10010];
vector<ll>v[10010];//循环节
struct node
{
    int pos;
    ll val;
};
ll cur[20010];
ll pre[20010];
ll dp[20010];
ll solve(int id,int c)
{
    int n=v[id].size();
    for(int i=1;i<=n;i++)
        cur[i]=v[id][i-1];
    for(int i=n+1;i<=2*n;i++)
        cur[i]=v[id][i-n-1];
    n*=2;
    pre[0]=0;
    for(int i=1;i<=n;i++)
        pre[i]=pre[i-1]+cur[i];
    /*for(int i=1;i<=n;i++)
        printf("%lld ",pre[i]);
    printf("\n");*/
    ll ans=0;
    deque<node>q;
    node temp;
    temp.pos=0;temp.val=0;
    q.push_back(temp);
    for(int i=1;i<=n;i++)
    {
        dp[i]=cur[i];
        while(!q.empty()&&(i-q.front().pos)>c)
            q.pop_front();
        if(!q.empty())
            dp[i]=max(dp[i],pre[i]-q.front().val);
        ans=max(ans,dp[i]);
        temp.pos=i;temp.val=pre[i];
        while(!q.empty()&&temp.val<=q.back().val)
            q.pop_back();
        q.push_back(temp);
    }
    return ans;
}
int main()
{
    int t,n,m,k;
    ll s;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++)
    {
        scanf("%d%lld%d%d",&n,&s,&m,&k);
        for(int i=0;i<n;i++)
            scanf("%lld",&a[i]);
        memset(vis,0,sizeof(vis));
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            if(!vis[i])
            {
                cnt++;
                for(int j=i;!vis[j];j=(j+k)%n)
                {
                    v[cnt].push_back(a[j]);
                    vis[j]=true;
                }
            }
        }
        /*for(int i=1;i<=cnt;i++)
        {
            for(int j=0;j<v[i].size();j++)
                printf("%lld ",v[i][j]);
            printf("\n");
        }*/
        ll tot=0;
        for(int i=1;i<=cnt;i++)
        {
            int len=v[i].size();
            int num=m/len;//圈数
            int c=m%len;//多的
            ll sum=0;
            for(int j=0;j<v[i].size();j++)
                sum+=v[i][j];
            //printf("num=%d c=%d sum=%lld\n",num,c,sum);
            ll temp1=solve(i,c);
            ll temp2=solve(i,len);
            ll ans1=max(0ll,sum)*num+temp1;//负环也有可能选几个成立
            ll ans2=max(0ll,sum)*max(0,num-1)+temp2;
            tot=max(tot,max(ans1,ans2));
        }
        //printf("tot=%lld\n",tot);
        printf("Case #%d: ",kase);
        if(tot>=s)printf("0\n");
        else printf("%lld\n",s-tot);
        for(int i=1;i<=cnt;i++)
            v[i].clear();
    }
    return 0;
}