// compile: make data
// run: time ./data < data.in
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x),__VA_ARGS__})
#define cmax(x,...) x=max({(x),__VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define uint unsigned long long
#define MAXN 200010

void monotonicity(vector<int> &dp, int L, int R, pair<int, int> itvl, pair<int, int> itvr, auto &update) {
    vector<int> target(R+1, -1);
    rep(i, itvl.first, itvl.second + 1) {
        int v = update(L, i);
        if (v == NaN) continue;
        dp[L] = v, target[L] = i;
    }
    rep(i, itvr.first, itvr.second + 1) {
        int v = update(R, i);
        if (v == NaN) continue;
        dp[R] = v, target[R] = i;
    }
    function<void(int, int, int, int)> solve = [&update, &target, &dp, &solve](int l, int r, int low, int high) {
        if (l > r) return;
        int mid = (l + r) / 2;
        if (!~target[mid]) {
            rep(i, low, high + 1) {
                int v = update(mid, i);
                if (v == NaN) continue;
                dp[mid] = v, target[mid] = i;
            }
        }
        solve(l, mid - 1, low, target[mid]);
        solve(mid + 1, r, target[mid], high);
    };
    solve(L, R, target[L], target[R]);
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, k; cin >> n >> k;
    vector<int> a(n+1);
    vector<vector<int>> suml(n+1, vector<int>(n+1)), sumr(n+1, vector<int>(n+1));
    rep(i, 1, n+1) cin >> a[i];
    rep(i, 1, n+1) rep(j, i+1, n+1) suml[i][j] = suml[i][j-1] + a[j] * (j - i);
    for (int i = n; i >= 1; --i) for (int j = i-1; j >= 1; --j) sumr[j][i] = sumr[j+1][i] + a[j] * (i - j);
    auto calc = [&](int l, int r) -> int {
        if (l == r) return 0;
        int mid = (l + r) / 2;
        return suml[l][mid] + sumr[mid+1][r];
    };
    vector<vector<int>> value(n+1, vector<int>(n+1));
    rep(i, 1, n+1) rep(j, i, n+1) value[i][j] = calc(i, j);
    vector<int> pre(n+1, INF), dp(n+1, INF);

    rep(i, 1, n+1) pre[i] = sumr[1][i];
    auto update = [&pre, &dp, &value](int i, int j) {
        int v = pre[j] + value[j][i];
        if (v < dp[i]) return v;
        else return NaN;
    };
    rep(it, 2, k+1) {
        monotonicity(dp, it, n, {1, it-1}, {1, n-1}, update);
        pre = dp;
    }
    int ans = INF;
    rep(i, 1, n+1) cmin(ans, dp[i] + suml[i][n]);
    cout << ans << endl;

    return 0;
}