这里不是个妹子，刚学C艹3天，绝对是个萌新

#include<bits/stdc++.h>
inline int read()
{
    int f=1,w=0;char x=0;
    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
    return w*f;
}
using namespace std;
int T,Maxnp,w,q[2001],l,r,f[2001][2001],ans;
int main(){
	T=read(),Maxnp=read(),w=read();
	memset(f,128,sizeof(f));
	for(int i=1;i<=T;i++)
	{
		int ap,bp,as,bs;
		ap=read(),bp=read(),as=read(),bs=read();
		for(int j=0;j<=as;j++) f[i][j]=-1*j*ap;
		for(int j=0;j<=Maxnp;j++) f[i][j]=max(f[i][j],f[i-1][j]);
		if(i<=w) continue; l=1,r=0;
		for(int j=0;j<=Maxnp;j++)
		{
			while(l<=r&&q[l]<j-as) l++;
			while(l<=r&&f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap) r--;
			q[++r]=j;
			if(l<=r) f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*ap-j*ap);
		}
		l=1,r=0;
		for(int j=Maxnp;j>=0;j--)
		{
			while(l<=r&&q[l]>j+bs) l++;
			while(l<=r&&f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp) r--;
			q[++r]=j;
			if(l<=r) f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*bp-j*bp);
		}
	}
	for(int i=0;i<=Maxnp;i++) ans=max(ans,f[T][i]);
	printf("%d\n",ans);
}