#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int maxm = 8;
const long long inf = 1e18;
 
int n, m, a[maxn], best[maxm][2];
long long c[maxn][maxn], dp[maxm][maxn];
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = i + 1, d = 1; j != i; j = (j + 1) % n, d++) {
            c[i][j] = c[i][(j + n - 1) % n] + 1LL * d * a[j];
        }
    }
 
    long long res = inf;
    for (int s = 0; s < n; s++) {
        for (int i = 0; i < n; i++) {
            dp[0][i] = c[s][(s + i) % n];
        }
        for (int i = 1; i <= m; i++) {
            best[i][0] = i - 1;
        }
        for (int d = 1; d < n; d++) {
            for (int l = 1; l < m && l + d < n; l++) {
                int r = l + d;
                int b = best[l][1 - d % 2];
                int e = best[l + 1][1 - d % 2];
                dp[l][r] = inf;
                for (int i = b; i <= e; i++) {
                    long long cur = dp[l - 1][i]
                                        + c[(s + i + 1) % n][(s + r) % n];
                    if (cur < dp[l][r]) {
                        dp[l][r] = cur;
                        best[l][d % 2] = i;
                    }
                }
            }
            best[m][d % 2] = m + d - 1;
        }
        res = min(dp[m - 1][n - 1], res);
    }
    cout << res << '\n';
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBtYXhuID0gMTAwNTsKY29uc3QgaW50IG1heG0gPSA4Owpjb25zdCBsb25nIGxvbmcgaW5mID0gMWUxODsKCmludCBuLCBtLCBhW21heG5dLCBiZXN0W21heG1dWzJdOwpsb25nIGxvbmcgY1ttYXhuXVttYXhuXSwgZHBbbWF4bV1bbWF4bl07CgppbnQgbWFpbigpIHsKICAgIGNpbiA+PiBuID4+IG07CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGNpbiA+PiBhW2ldOwogICAgfQoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgZm9yIChpbnQgaiA9IGkgKyAxLCBkID0gMTsgaiAhPSBpOyBqID0gKGogKyAxKSAlIG4sIGQrKykgewogICAgICAgICAgICBjW2ldW2pdID0gY1tpXVsoaiArIG4gLSAxKSAlIG5dICsgMUxMICogZCAqIGFbal07CiAgICAgICAgfQogICAgfQoKICAgIGxvbmcgbG9uZyByZXMgPSBpbmY7CiAgICBmb3IgKGludCBzID0gMDsgcyA8IG47IHMrKykgewogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgICAgIGRwWzBdW2ldID0gY1tzXVsocyArIGkpICUgbl07CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG07IGkrKykgewogICAgICAgICAgICBiZXN0W2ldWzBdID0gaSAtIDE7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGQgPSAxOyBkIDwgbjsgZCsrKSB7CiAgICAgICAgICAgIGZvciAoaW50IGwgPSAxOyBsIDwgbSAmJiBsICsgZCA8IG47IGwrKykgewogICAgICAgICAgICAgICAgaW50IHIgPSBsICsgZDsKICAgICAgICAgICAgICAgIGludCBiID0gYmVzdFtsXVsxIC0gZCAlIDJdOwogICAgICAgICAgICAgICAgaW50IGUgPSBiZXN0W2wgKyAxXVsxIC0gZCAlIDJdOwogICAgICAgICAgICAgICAgZHBbbF1bcl0gPSBpbmY7CiAgICAgICAgICAgICAgICBmb3IgKGludCBpID0gYjsgaSA8PSBlOyBpKyspIHsKICAgICAgICAgICAgICAgICAgICBsb25nIGxvbmcgY3VyID0gZHBbbCAtIDFdW2ldCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICArIGNbKHMgKyBpICsgMSkgJSBuXVsocyArIHIpICUgbl07CiAgICAgICAgICAgICAgICAgICAgaWYgKGN1ciA8IGRwW2xdW3JdKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGRwW2xdW3JdID0gY3VyOwogICAgICAgICAgICAgICAgICAgICAgICBiZXN0W2xdW2QgJSAyXSA9IGk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGJlc3RbbV1bZCAlIDJdID0gbSArIGQgLSAxOwogICAgICAgIH0KICAgICAgICByZXMgPSBtaW4oZHBbbSAtIDFdW24gLSAxXSwgcmVzKTsKICAgIH0KICAgIGNvdXQgPDwgcmVzIDw8ICdcbic7CgogICAgcmV0dXJuIDA7Cn0K

NiAyCjIKNQo0CjIKNgoyCg==

6 2
2
5
4
2
6
2