悬 1~2 关

#include<bits/stdc++.h>
#define int1 long long
#define N 50000
#define M 2000
#define INF 1145141919810114514
#define mod 1000000007
#define Getchar getchar_unlocked
#define ls (d << 1)
#define rs (d << 1 | 1)
#define P pair<int1,int1>
using namespace std;
int1 day,m,W,i,ii,j,ap,bp,as,bs,ans;
int1 weight[N + 5],value[N + 5],n,tota[M + 5],totb[M + 5];
int1 dp[M + 5][M + 5],wtf[M + 5],f[M + 5];
int1 read(){
	int1 x = 0,f = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-'){
			f = -1;
		}
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
bool ischar(int1 x,char ch){
	return (((x & 1) && ch >= 'A' && ch <= 'Z') || ((x & 2) && ch >= 'a' && ch <= 'z') || ((x & 4) && ch >= '0' && ch <= '9') || 
	((x & 8) && ch != ' ' && ch != '\n' && ch != '\r') || ((x & 16) && ch != '\n' && ch != '\r'));
}
void uprint(int1 x){
	if(x > 9){
		uprint(x / 10);
	}
	putchar(x % 10 ^ 48);
	return ;
}
void print(int1 x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	uprint(x);
	return ;
}
void ps(int1 x){
	print(x);
	putchar(' ');
	return ;
}
void pe(int1 x){
	print(x);
	putchar('\n');
	return ;
}
int main(){
	day = read(),m = read(),W = read();
	for(i = 1; i <= day; i++){
		ap = read(),bp = read(),as = read(),bs = read();
		//二进制优化 
		for(j = 1; j <= as; j <<= 1){
			weight[++n] = j,value[n] = j * ap;
			as -= j;
		}
		if(as > 0){
			weight[++n] = as,value[n] = as * ap;
		}
		tota[i] = n;//记录位置
		for(j = 1; j <= bs; j <<= 1){
			weight[++n] = j,value[n] = j * bp;
			bs -= j;
		}
		if(bs > 0){
			weight[++n] = bs,value[n] = bs * bp;
		}
		totb[i] = n;//记录位置
	}
	for(i = 0; i <= day; i++){
		for(j = 0; j <= m; j++){
			dp[i][j] = -INF;
		}
	}
	dp[0][0] = 0;//dp[i][j]表示第 i 天手上有 j 股的最大价值 
	for(i = 1,ii = 1; i <= day; i++){
		int1 l = max(0ll,i - W - 1);
		for(j = 0; j <= m; j++){
			f[j] = dp[i - 1][j];
		}
		f[0] = 0;
		for(; ii <= tota[i]; ii++){
			for(j = weight[ii]; j <= m; j++){
				f[j] = max(f[j],dp[l][j - weight[ii]] - value[ii]);//买 
			}
		}
		for(; ii <= totb[i]; ii++){
			for(j = weight[ii]; j <= m; j++){
				f[j - weight[ii]] = max(f[j - weight[ii]],dp[l][j] + value[ii]);//卖 
			}
		}
		for(j = 0; j <= m; j++){
			dp[i][j] = f[j];//合并
		}
	} 
	for(i = 0; i <= m; i++){
		ans = max(ans,dp[day][i]);//统计答案 
	}
	pe(ans);
	return 0;
}