#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <cstring>
#define MAX 10010
using namespace std;

int k;
long long c[MAX], dp[MAX][2001];

long long solved(int n){
    long long best = LLONG_MAX;
    for(int i = 1; i <= k; i++){
        long long cur = 0;
        int j, ant;
        for(int ini = 1; ini <= (i+1); ini++){
            cur = 0;
            for(j = ini; (j+i) <= n; j += (2*i+1)){
//                cout << j << " ";
                cur += c[j];
                ant = j;
            }    
//            cout << " final " <<j << endl;
            if((ant + i) >= n){
//                cout << cur << endl;
                best = min(cur, best);
            }
            
        }
    }
    return best;
}

long long rec(int n, int dist){
    if(dp[n][dist] < 0){
        if(n == 0){
            if(dist < k)
                return dp[n][dist] = 100000000000000LL;
            return dp[n][dist] = 0;
        }
        long long cost = rec(n-1, 2*k) + c[n], n_cost = LLONG_MAX;
        if(dist > 0){
            n_cost = rec(n-1, dist-1);
        }
        return dp[n][dist] = min(cost, n_cost);
    }
    return dp[n][dist];
}

long long solve(int n){
    long long ans = LLONG_MAX;
    if(k == 0){
        ans = 0;
        for(int i = 1; i <= n; i++)
            ans += c[i];
        return ans;
    }    
    
    return max(rec(n, k), solved(n));
}

int main() {
    int n;
    while(cin >> n >> k){
        memset(dp, -1, sizeof(dp));
        for(int i = 1; i <= n; i++)
            cin >> c[i];        
        cout << solve(n) << endl;
    }
    return 0;
}