蒟蒻求助 50pts wa#1,3,4,8,9

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
#define int long long

int f[maxn][maxn],ap[maxn],bp[maxn],as[maxn],bs[maxn],t,w,p;
deque<int>q;
signed main()
{
	cin>>t>>p>>w;
	for(int i=1;i<=t;i++) cin>>ap[i]>>bp[i]>>as[i]>>bs[i];
	memset(f,0xcf,sizeof f);
	for(int i=0;i<=t;i++) f[i][0]=0;
	for(int i=1;i<=t;i++){
		for(int j=0;j<=as[i];j++) f[i][j]=-ap[i]*j;
		for(int j=p;j>=0;j--) f[i][j]=max(f[i][j],f[i-1][j]);
		if(i-w>=1){
			q.clear();
			for(int j=0;j<=p;j++){
				while(!q.empty() && j-q.front()>as[i]) q.pop_front();
				while(!q.empty() && f[i-w-1][j]+ap[i]*j>=f[i-w-1][q.back()]+ap[i]*q.back()) q.pop_back();
				q.push_back(j);
				//cout<<q.back()<<endl;
				f[i][j]=max(f[i][j],f[i-w-1][q.front()]-ap[i]*(j-q.front()));
				//cout<<f[i][j]<<endl;
			}
			q.clear();
			for(int j=p;j>=0;j--){
				while(!q.empty() && q.front()>j+bs[i]) q.pop_front();
				while(!q.empty() && f[i-w-1][j]+bp[i]*j>=f[i-w-1][q.back()]+bp[i]*q.back()) q.pop_back();
				q.push_back(j);
				f[i][j]=max(f[i][j],f[i-w-1][q.front()]+bp[i]*(q.front())-j);
			}
		}
	}
	cout<<f[t][0]<<endl;
	return 0;
}