WSEQ2

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define task ""
using namespace std;
using ll = int;
using ld = long double;

const int N = 4e2 + 2;
const ll Inf = 1e18;
int n, m, k;
ll a[N];
ll dp[N][N][N];

void Read(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
}

/// f(i, j, u) : số thứ i đã chọn j thằng và u thằng quan trọng
/// TH1 : K chọn i : f(i, j, u) = f(i - 1, j, u) + ((i - j) % k == 0 ? 0 : a[i]);
/// TH2 : Chọn i :
///         a - Không chọn i vào u : f(i, j, u) = f(i - 1, j - 1, u)
///         b - Chọn i vào u : f(i, j, u) = f(i - 1, j - 1, u - 1) + a[i]

ll &f(int x, int y, int z){
    return dp[x][y][z];
}

void Solve(){
    fill_n(&dp[0][0][0], N * N * N, Inf);
    dp[0][0][0] = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= m; ++j)
            for(int u = 0; u <= j; ++u){
                ///TH1
                f(i, j, u) = f(i - 1, j, u) + ((i - j) % k == 0 ? 0 : a[i]);
                ///TH2
                if(j){
                    //a
                    f(i, j, u) = min(f(i, j, u), f(i - 1, j - 1, u));
                    //b
                    if(u)
                        f(i, j, u) = min(f(i, j, u), f(i - 1, j - 1, u - 1) + a[i]);
                }
            }
    ll ans = Inf;
    for(int i = 0; i <= m; ++i)
        ans = min(ans, dp[n][i][i - (n / k - (n - i) / k)]);
    cout << ans;
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); if(fopen(task".INP", "r"))
    freopen(task".INP", "r", stdin),
    freopen(task".OUT", "w", stdout);
    Read();
    Solve();
}