#include #include #include #include #include #include #pragma GCC optimize("O2") using ll = long long int; using P = std::pair; const int INF = (1<<30); const ll INFLL = (1ll<<60); const ll MOD = (ll)(1e9+7); #define l_ength size void mul_mod(ll& a, ll b){ a *= b; a %= MOD; } void add_mod(ll& a, ll b){ a = (a pq; int main(void){ int n,m,i; ll ans = -INFLL; std::fill(dp[0],dp[225816],-INFLL); std::cin >> n >> m; --m; dp[0][0] = 0ll; pq.push(P(0ll,0)); for(i=0; i> a[i]; s[i+1] = s[i] + a[i]; } for(i=1; i<=n; ++i){ while(pq.top().second < i-m){ pq.pop(); } dp[i][1] = pq.top().first + s[i]; dp[i][0] = std::max(dp[i-1][0],dp[i-1][1]); pq.push(P(dp[i][0]-s[i],i)); } for(i=0; i<=n; ++i){ ans = std::max(ans,std::max(dp[i][0],dp[i][1])); } std::cout << ans << std::endl; return 0; }