记$a-ap_i,b=as_i,c=bp_i,d=bs_i,t=w+1$

$f_{i,j}=\max\begin{cases}f_{i-1,j}\\ -a*j(j\le b\& i\le t)\\f_{i-t,k}-a*j+a*k(0\le k<j\&j-k\le b)\\f_{i-1,k}-c*j+c*k(j<k\le maxp\& k-j\le d)\\ \end{cases}$

后两个明显可以用单调队列优化。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=2e3+5;
inline void qr(int &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N][N],ap[N],bp[N],as[N],bs[N],q[N];
int main()
{
    int n,mxp,t;qr(n),qr(mxp),qr(t);++t;
    f[0][0]=-N*N;for(int j=1;j<=mxp+1;j++)f[0][j]=f[0][j-1];
    for(int i=1;i<=n;i++)qr(ap[i]),qr(bp[i]),qr(as[i]),qr(bs[i]);
    for(int i=1;i<=n;i++)
    {
        memcpy(f[i],f[i-1],sizeof(f[i]));
        int a=ap[i],b=as[i],c=bp[i],d=bs[i],l,r;
        if(i<=t)for(int j=0;j<=b;j++)f[i][j]=max(f[i][j],-a*j);
        else
        {
            int l=1,r=1;q[1]=0; 
            for(int j=1;j<=mxp;j++)
            {
                while(l<=r&&j-q[l]>b)++l;
                f[i][j]=max(f[i][j],f[i-t][q[l]]-a*j+a*q[l]);
                while(l<=r&&f[i-t][q[r]]+a*q[r]<=f[i-t][j]+a*j)--r;
                q[++r]=j;
            }
            l=1;r=1;q[1]=mxp+1;
            for(int j=mxp;~j;j--)
            {
                while(l<=r&&q[l]-j>d)++l;
                f[i][j]=max(f[i][j],f[i-t][q[l]]-c*j+c*q[l]);
                while(l<=r&&f[i-t][q[r]]+c*q[r]<=f[i-t][j]+c*j)--r;
                q[++r]=j;
            }
        }
    }
    qw(f[n][0]);puts("");
    return 0;
}