题目处理起来比较棘手，要分成两个步骤来完成。
先描述一下题意：
n个数字排列在一个圆上，我们可以以任意一个数字为起点走不超过m步，每步都要走k格，要使走过的格子里的数字总和最大
步骤一：
先找出循环节，我们可以得知循环节的长度为n/gcd(n,k)，一共有gcd(n,k)个循环节，我们每次都取出循环节内的数字进行处理，由于每次走完一个循环节的总和相同，所有我们只要处理最大长度为m%(n/gcd(n,k))的最长子段即可。
步骤二：
处理最长子段和，但这里会发现，我们步骤一的处理出现了问题，借用discuss里的数据说明一下：
1
5 100 12 1
-10 1 2 3 5
对于这组数据，我们认为只要处理长度为2的最长子段和即可，那么我们的答案为1*2+3+5=10
但这并不是最小答案，存在解 1 2 3 5 -10 1 2 3 5 = 12
所以，不能认为所有循环节都进行默认求和，我们要处理的最大长度应为m%(n/gcd(n,k))+n/gcd(n,k) (如果题目给出的序列够长的话）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<iomanip>
#include<cctype>
using namespace std;
#define ll long long
#define edl putchar('
')
#define sscc ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define FORLL(i,a,b) for(ll i=a;i<=b;i++)
#define ROFLL(i,a,b) for(ll i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
#define zero(x)(((x)>0?(x):-(x))<eps)
const int MAXN=2e4+5;
const int INF=1<<30;
const long long mod=-(ll)1<<60;
const double eps=1e-8;
ll a[MAXN],b[MAXN],s[MAXN],ans,sum,s1,k,m,p;
int n,T,t,l,z,cas=0;
struct node
{
ll val;
int id;
}q[MAXN];
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
ll solve()
{
ll ret=mod;
FOR(i,l+1,3*l)
b[i]=b[i-l];
mst(s);
FOR(i,1,3*l)
s[i]=s[i-1]+b[i];
int li=0;
int ri=0;
int head=1;
int tail=0;
tail+=1;
q[tail].val=0;
q[tail].id=0;
FOR(i,1,l+z-1)
{
if(s[i]-q[head].val>=ret)
{
if(s[i]-q[head].val==ret && q[head].id+1<li)
{
ri=i;
li=q[head].id+1;
}
else if(s[i]-q[head].val==ret && (q[head].id+1==li) && (ri-li+1>i-q[head].id))
{
ri=i;
li=q[head].id+1;
}
else if(s[i]-q[head].val>ret)
{
ret=s[i]-q[head].val;
li=q[head].id+1;
ri=i;
}
}
while(tail>=head && q[tail].val>s[i])
tail-=1;
tail+=1;
q[tail].val=s[i];
q[tail].id=i;
if(i>=z)
{
while(tail>=head && q[head].id<i-z+1)
head+=1;
if(q[head].id>=l)
break;
}
}
return ret;
}
int main()
{
scanf("%d",&T);
while(T--)
{
ans=mod;
scanf("%d%lld%lld%lld",&n,&p,&m,&k);/*个数 修正 走m步 一次走k格 */
FOR(i,0,n-1) scanf("%lld",&a[i]);
t=gcd(n,k);
l=n/t;
z=m%l;
if(m>=l)
z+=l;
FOR(J,0,t-1)
{
s1=0;
sum=mod;
FORLL(i,0,l-1)
s1+=a[(J+i*k)%n];
s1=max((ll)0,s1);
if(m>=l)
s1*=(ll)(m/l-1);
else
s1=0;
FORLL(i,0,l-1)
b[i+1]=a[(J+i*k)%n];
ans=max(ans,s1+solve());
}
printf("Case #%d: %lld
",++cas,max((ll)0,p-ans));
}
}