1. #include <cstdio>
    2. #include <algorithm>
    3. #include <cstring>
    4. #include <cstdlib>
    5. #include <iostream>
    6. using namespace std;
    7. #define int long long 
    8. inline int gi(){
    9.     char tmp=getchar();int ans=0;
    10.     while(!isdigit(tmp)) tmp=getchar();
    11.     while(isdigit(tmp)){
    12.         ans = ans * 10 + tmp - '0';
    13.         tmp = getchar();
    14.     }
    15.     return ans;
    16. }
    17. const int N = 1e7;
    18. int F[N],Sum[N];
    19. int Q[N];
    20. signed main()
    21. {
    22. #ifdef TSUKIAKIOI
    23.     freopen("data.in","r",stdin);
    24. #endif
    25.     int n,m;n=gi(),m=gi();
    26.     for(int i=1;i<=n;++i){
    27.         Sum[i] = gi();
    28.         Sum[i] += Sum[i-1];
    29.     }
    30.     int head=0,tail=-1;
    31.     Q[++tail] = 0;
    32.     for(int i=1;i<=n+1;++i){
    33.         while(head <= tail && i - m - 1 > Q[head]) head++;
    34.         F[i] = F[Q[head]] + Sum[i-1]-Sum[Q[head]];
    35.         while(head <= tail && F[Q[tail]]-Sum[Q[tail]] <= F[i] - Sum[i]) tail--;
    36.         Q[++tail]=i;
    37.     }
    38.     printf("%lld",F[n+1]);
    39.     return 0;
    40. }