o58_oct_c2_defense

#include <bits/stdc++.h>

using namespace std;
const int N = 3e3 + 10;
const int INF = 1e9;
int ar[N], dp[N];
int n, k;

int main(){

    scanf("%d%d", &n, &k);

    for(int i=1;i<=n;i++){
        scanf("%d", &ar[i]);
        dp[i] = INF;
    }

    if(n <= k){
        dp[1] = ar[1];
        int mn = ar[1];
        int ans = INF;
        for(int i=2;i<=n;i++){
            ans = min(ans, ar[i] + mn);
            mn = min(mn, ar[i]);
        }
        printf("%d", ans);
    }
    else if(n >= 2 * k){
        dp[1] = ar[1];
        int mn = ar[1];
        for(int i=2;i<=k;i++){
            dp[i] = ar[i] + mn;
            mn = min(mn, ar[i]);
        }

        for(int i=k+1;i<n;i++){
            for(int j=i-k+1;j<i;j++){
                dp[i] = min(dp[i], ar[i] + dp[j]);
            }
        }

        int ans = INF;
        for(int i=n-k+2;i<=n;i++){
            for(int j=i-k+1;j<i;j++){
                ans = min(ans, ar[i] + dp[j]);
            }
        }
        printf("%d", ans);
    }
    else{
        dp[1] = ar[1];
        int mn = ar[1];
        for(int i=2;i<=k;i++){
            dp[i] = ar[i] + mn;
            mn = min(mn, ar[i]);
        }

        int ans = INF;
        for(int i=k+1;i<=n;i++){
            for(int j=i-k+1;j<i;j++){
                ans = min(ans, ar[i] + dp[j]);
            }
        }
        printf("%d", ans);
    }

    return 0;
}