#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;
}