#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int a[N], n, m, ans = -1e18, sum[N];
deque<int>q;
signed main(void) {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	for (int i = 1; i <= n; i++) {
		while (q.size() && sum[i - 1] <= sum[q.back()]) q.pop_back();
		q.push_back(i - 1);
		while (q.size() && q.front() < i - m) q.pop_front();
		ans = max(ans, sum[i] - sum[q.front()]);
	}
	cout << ans << '\n';
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6+5;
int n,L,R;
int a[N],f[N],q[N],tail=-1,head=0;
signed main(){
	cin>>n>>L>>R;
	for(int i=0;i<=n;i++){
		cin>>a[i];
	}
	memset(f,0xcf,sizeof(f));
	f[0] = a[0];
	int res = -1e18;
	for(int i=L;i<=n+R;i++){
		//i-L入队
		while(tail>=head && f[i-L]>=f[q[tail]])--tail;
		q[++tail] = i-L;
		while(tail>=head && q[head]<i-R)++head;
		int j = q[head];
		f[i] = f[q[head]]+a[i];
		if(i>=n)res = max(res,f[i]);
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,k,f[N],sum[N],q[N],tail=-1,head=0;
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>sum[i];
		sum[i]+=sum[i-1];
	}
	int res = -1e18;
	q[++tail] = 0;
	for(int i=1;i<=n;i++){
		//1.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];
		if(j==0)f[i] = sum[i];
		else f[i] = f[j-1]+sum[i]-sum[j];
		res = max(res,f[i]);
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
int n,m,a[N][N],k,t;
int f[N][N*2],q[N],tail=-1,head=0;
signed main(){
	cin>>n>>m>>k>>t;
	for(int i=1;i<=k;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y] = z;
	}
	int res = 0;
	for(int i=1;i<=m;i++)f[1][i] = a[1][i];
	for(int i=2;i<=n;i++){
		tail = -1;
		head = 0;
		memset(q,0,sizeof(q));
		for(int s=1;s<=t;s++){
			while(tail>=head && f[i-1][s]>=f[i-1][q[tail]])--tail;
			q[++tail] = s;
		}
		for(int j=1;j<=m;j++){
			while(tail>=head && f[i-1][j+t]>=f[i-1][q[tail]])--tail;
			q[++tail] = j+t;
			while(tail>=head && abs(j-q[head])>t)head++;
			int s = q[head];
			f[i][j] = f[i-1][s]+a[i][j];
			res = max(res,f[i][j]);
		}
	}
	cout<<res<<endl;
	return 0;
}