#include <stdio.h> #define N 2001 #define inf 10000000 #define max(a,b) ((a)>(b)?(a):(b)) int f[N][N],q[N],id[N]; int main(){ int t,n,maxp,w,ap,bp,as,bs; scanf("%d",&t); while(t--){ scanf("%d%d%d",&n,&maxp,&w); for(int i=0;i<n;++i){ scanf("%d%d%d%d",&ap,&bp,&as,&bs); for(int j=0;j<=maxp;++j)f[i][j]=-inf; if(i<=w)for(int j=0;j<=as;++j)f[i][j]=-ap*j; if(i>0)for(int j=0;j<=maxp;++j)f[i][j]=max(f[i][j],f[i-1][j]); if (i==0||i<=w) continue; for(int j=0,l=0,r=-1;j<=maxp;++j){ int tmp=f[i-w-1][j]+j*ap; while(l<=r&&q[r]<tmp)--r; q[++r]=tmp,id[r]=j; while(l<=r&&id[l]+as<j)++l; f[i][j]=max(f[i][j],q[l]-j*ap); } for(int j=maxp,l=0,r=-1;j>=0;--j){ int tmp=f[i-w-1][j]+j*bp; while(l<=r&&q[r]<tmp)--r; q[++r]=tmp,id[r]=j; while(l<=r&&id[l]-bs>j)++l; f[i][j]=max(f[i][j],q[l]-j*bp); } } int ans=0; for(int i=0;i<=maxp;++i)ans=max(ans,f[n-1][i]); printf("%d\n",ans); } return 0; }
|