link

50pts

#include<bits/stdc++.h>
#define ll long long
#define il inline
const ll N = 100100;
const ll inf = 2e18;
using namespace std;

void read(ll &x) {
	x = 0;
	char c = getchar();
	ll f = 0;
	for (;!isdigit(c); c = getchar())
		f |= c == '-';
	for (; isdigit(c); c = getchar())
		x = x*10 + ( c ^ '0');
	if (f) x = -x;
}

ll n, k, e[N], zong;
ll f[N], ans = inf;
struct node{
	ll vel, it;
} v[N];

int main() {
	read(n); read(k);
	for (int i = 1; i <= n; i++) {
		read(e[i]);
		zong += e[i];
	}
/*	for (int i = 1; i <= n; i++) { // n
		ll res = inf;
		for (int j = max(0LL, i-k-1); j <= i-1; j++) { // k
			res = min(res, f[j]);
		}
		f[i] = res + e[i]; 
	} O(nk) 原始DP*/
	ll head = 1, endr = 0;
	for (int i = 2; i <= n; i++) { // 单调队列优化
		while (head <= endr && (v[endr].vel >= f[i-1])) {
			endr --;
		}
		v[++endr].vel = f[i-1];
		v[endr].it = i-1;
		while (head <= endr && (i - v[head].it > k))
			head ++;
		ll res = v[head].vel;
		f[i] = res + e[i]; 
	}
	for (int i = n-k; i <= n; i++) {
		ans = min(f[i], ans);
	}
	cout << zong - ans << '\n';
	return 0;
}

QWQ