#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,a[N],k;
int q[N],tail=-1,head=0;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		//1.队尾出队
		while(tail>=head && a[i]<=a[q[tail]])--tail;
		q[++tail] = i;
		while(tail>=head && i-q[head]+1>k)head++;
		if(i>=k)cout<<a[q[head]]<<" ";
	}
	cout<<endl;
	tail = -1,head = 0;
	for(int i=1;i<=n;i++){
		while(tail>=head && a[i]>=a[q[tail]])tail--;
		q[++tail] = i;
		while(tail>=head && i-q[head]+1>k)head++;
		if(i>=k)cout<<a[q[head]]<<" ";
	}
	return 0;
}

/*
f[i] = sum[i]-sum[j]  i-k<=j<i
选j+1到i块蛋糕 i-j<=k  j>=i-k
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int n,a[N],sum[N],k;
int q[N],tail=-1,head=0;
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i] = sum[i-1]+a[i];
	}
	int res = -1e18;
	for(int i=1;i<=n;i++){
		while(tail>=head && sum[i-1]<=sum[q[tail]])tail--;
		q[++tail] = i-1;
		while(tail>=head && q[head]<i-k)head++;
		res = max(res,sum[i]-sum[q[head]]);
	}
	cout<<res<<endl;
	return 0;
}

/*
f[i] = f[i-1]+x,f[j]+y+2*j*x-i*x  i/2<=j<i
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7+5;
int n,x,y,f[N];
int q[N],tail=-1,head=0;
signed main(){
	cin>>n>>x>>y;
	f[1] = x;
	
	for(int i=2;i<=n;i++){
		while(tail>=head && f[i-1]+2*(i-1)*x<=f[q[tail]]+2*q[tail]*x)--tail;
		q[++tail] = i-1;
		while(tail>=head && q[head]<i/2.0)head++;
		f[i] = min(f[i-1]+x,f[q[head]]+y+(2*q[head]-i)*x);
	}
	cout<<f[n]<<endl;
	return 0;
}

/*
f[i]前i头奶牛的最大效率
//i-j<=k
f[i] = f[j-1]-sum[j]+ (sum[i])   i-k<=j<=i
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N =1e5+5;
int n,k,a[N],sum[N];
int q[N],tail=-1,head=0,f[N];
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>sum[i];
		sum[i]+=sum[i-1];
	}
	q[++tail] = 0;
	for(int i=1;i<=n;i++){
		while(tail>=head && f[i-1]-sum[i]>=f[q[tail]-1]-sum[q[tail]])--tail;
		q[++tail] = i;
		while(tail>=head && q[head]<i-k)head++;
		int j = q[head];
		f[i] = f[j-1]+sum[i]-sum[j];
	}
	cout<<f[n]<<endl;
	return 0;
}

/*
f[i][j]第i天持有j张股票的时候赚的最多的钱
f[i][j] = -Ap[i]*j
f[i][j] = f[i-1][j]

f[i][j] = f[i-w-1][k]+k*Ap[i] -j*Ap[i]      j-As[i]<=k<=j

f[i][j] = f[i-w-1][k]+k*Bp[i]-j*Bp[i]       j+Bs[i]>=k>=j
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2005;
int n,MaxP,w;
int As[N],Bs[N],Ap[N],Bp[N],f[N][N];
int q[N],tail=-1,head=0;
signed main(){
	cin>>n>>MaxP>>w;w++;
	for(int i=1;i<=n;i++){
		cin>>Ap[i]>>Bp[i]>>As[i]>>Bs[i];
	}
	memset(f,0xcf,sizeof(f));
	f[0][0] = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=MaxP;j++){
			if(j<=As[i])f[i][j] = -Ap[i]*j;
			f[i][j] = max(f[i][j],f[i-1][j]);
		}
		if(i>=w){
			tail=-1,head=0;
			for(int j=0;j<=MaxP;j++){
				while(tail>=head && f[i-w][j]+j*Ap[i]>=f[i-w][q[tail]]+q[tail]*Ap[i])--tail;
				q[++tail] = j;
				while(tail>=head && q[head]<j-As[i])head++;
				f[i][j] = max(f[i][j],f[i-w][q[head]]+q[head]*Ap[i]-j*Ap[i]);
			}
			tail=-1,head=0;
			for(int j=MaxP;j>=0;j--){
				while(tail>=head && f[i-w][j]+j*Bp[i]>=f[i-w][q[tail]]+q[tail]*Bp[i])--tail;
				q[++tail] = j;
				while(tail>=head && q[head]>j+Bs[i])head++;
				f[i][j] = max(f[i][j],f[i-w][q[head]]+Bp[i]*q[head]-j*Bp[i]);
			}
		}
	}
	int res = -1e19;
	for(int i=0;i<=MaxP;i++){
		res = max(res,f[n][i]);
	}
	cout<<res<<endl;
	return 0;
}