#include // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair; const ll INF=4e18; void print0(){}; template void print0(H h,T... t){cout<void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);} void perr0(){}; template void perr0(H h,T... t){cerr<void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);} void ioinit() { cout< data; vector updates; LST default_value; lazy_segment_tree(ll n) { default_value = add_default(); ll siz = 1; while (siz < n) { siz = siz * 2; } data.resize(siz * 2, default_value); updates.resize(data.size(), default_value); size = siz; } ~lazy_segment_tree() {} //-------- LST compare(LST x, LST y) { return max(x, y); } LST compare_default() { return -INF; } LST add(LST x, LST y) { return x + y; } LST add_default() { return 0; } LST evaluate(LST u, ll l, ll r) { return u; } LST transferred(LST vl, LST vr, ll l, ll r, ll a, ll b, ll k) { return add(compare(vl, vr), updates[k]); } //-------- void update(ll a, ll b, LST value) { if (a > b || a > size || b < 0) { return; } if (a < 0) { a = 0; } if (b > size) { b = size; } update_open(a, b + 1, 0, 0, size, value); } void update_open(ll a, ll b, ll k, ll l, ll r, LST value) { if (r <= a || b <= l) { // 共通要素がない return; } if (k >= size - 1) { // 末端 data[k] = add(data[k], evaluate(value, l, r)); return; } // 末端でないとき、一旦現在のupdatesを払い出し ll lk = 2 * k + 1; ll rk = 2 * k + 2; ll mid = (l + r) / 2; if (rk >= size - 1) { data[lk] = add(data[lk], evaluate(updates[k], l, mid)); data[rk] = add(data[rk], evaluate(updates[k], mid, r)); } else { updates[lk] = add(updates[lk], updates[k]); updates[rk] = add(updates[rk], updates[k]); } if (a <= l && r <= b) { // 完全に含んでいる data[k] = compare(add(data[lk], evaluate(updates[lk], l, mid)), add(data[rk], evaluate(updates[rk], mid, r))); updates[k] = value; } else { // 一部含む update_open(a, b, 2 * k + 1, l, mid, value); update_open(a, b, 2 * k + 2, mid, r, value); updates[k] = add_default(); data[k] = transferred(add(data[lk], evaluate(updates[lk], l, mid)), add(data[rk], evaluate(updates[rk], mid, r)), l, r, a, b, k); } } LST query_open(ll a, ll b, ll k, ll l, ll r) { if (r <= a || b <= l) { // 共通要素がない return compare_default(); } if (a <= l && r <= b) { // 完全に含んでいる return add(data[k], evaluate(updates[k], l, r)); } if (k >= size - 1) { // 末端であるとき return data[k]; } // 伝播すべき値がある LST vl = query_open(a, b, k * 2 + 1, l, (l + r) / 2); LST vr = query_open(a, b, k * 2 + 2, (l + r) / 2, r); return transferred(vl, vr, l, r, a, b, k); } LST query(ll a, ll b) { return query_open(a, b + 1, 0, 0, size); } }; int main() { ioinit(); cin >> N >> K; for (ll i = 1; i <= N; i++) { cin >> A[i]; } for (ll i = 1; i <= N; i++) { cum[i] = A[i] + cum[i - 1]; } auto dpseg = lazy_segment_tree(N + 2); for (ll i = 1; i <= N + 1; i++) { if (i - K < 1) { dpseg.update(i, i, cum[i - 1]); } else { ll cur = dpseg.query(i - K, i - 1); dpseg.update(i, i, cur); } dpseg.update(1, i - 1, A[i]); } print(dpseg.query(N + 1, N + 1)); return 0; }