E

#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<ii, ii> iii;
int MOD = 1e9 + 9;
const ld E = 1e-9;
#define null NULL
#define ms(x) memset(x, 0, sizeof(x))
#ifndef LOCAL
#define endl "\n"
#endif
#ifndef LONG_LONG_MAX
#define LONG_LONG_MAX LLONG_MAX
#endif
#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define _read(x) freopen(x, "r", stdin)
#define _write(x) freopen(x, "w", stdout)
#define files(x) _read(x ".in"); _write(x ".out")
#define filesdatsol(x) _read(x ".DAT"); _write(x ".SOL")
#define output _write("output.txt")
#define input _read("input.txt")
#define prev time_prev
#ifndef M_PI
#define M_PI acos(-1)
#endif
#define remove tipa_remove
#define next tipa_next
#define left tipa_left
#define right tipa_right
#define mod % MOD
#define y1 hello_world
unsigned char ccc;
bool _minus = false;
template<typename T>
inline T sqr(T t) {
    return (t * t);
}
inline void read(ll &n) {
    n = 0;
    _minus = false;
    while (true) {
        ccc = getchar();
        if (ccc == ' ' || ccc == '\n')
            break;
        if (ccc == '-') {
            _minus = true;
            continue;
        }
        n = n * 10 + ccc - '0';
    }
    if (_minus)
        n *= -1;
}
inline bool read(int &n) {
    n = 0;
    _minus = false;
    while (true) {
        ccc = getchar();
        if (ccc == ' ' || ccc == '\n') {
            if (ccc == '\n')
                return true;
            break;
        }
        if (ccc == '-') {
            _minus = true;
            continue;
        }
        n = n * 10 + ccc - '0';
    }
    if (_minus)
        n *= -1;
    return false;
}
char wwww[19];
int kkkk;
inline void write(ll y) {
    long long x = y;
    kkkk = 0;
    if (x < 0) {
        putchar('-');
        x *= -1;
    }
    if (!x)
        ++kkkk, wwww[kkkk] = '0';
    else
        while (x) {
            ++kkkk;
            wwww[kkkk] = char(x % 10 + '0');
            x /= 10;
        }
    for (int i = kkkk; i >= 1; --i)
        putchar(wwww[i]);
}

#ifdef LOCAL
#define DEBUG
#endif

#ifdef DEBUG
#define dbg if(1)
#else
#define dbg if(0)
#endif

int n, m;

const int MAX_N = 8e3 + 10;
const int MAX_M = 8e2 + 10;

ll dp[MAX_N][MAX_M];

int c[MAX_N][MAX_M];

ll ar[MAX_N];
ll sum[MAX_N];

void solve(int h, int l, int r, int tl, int tr){
    if(l > r)
        return;
    int x = (l + r) >> 1;
    c[x][h] = -1;
    for(int i = tl; i <= tr && i < x; i++){
        ll res = dp[i][h - 1] + (sum[x] - sum[i]) * 1LL * (x - i);
        if(res < dp[x][h]){
            dp[x][h] = res;
            c[x][h] = i;
        }
    }
    assert(c[x][h] != -1);
    solve(h, l, x - 1, tl, c[x][h]);
    solve(h, x + 1, r, c[x][h], tr);
}

int main() {
    sync;
    srand(time(NULL));
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL
    input;
#else

#endif

    cin >> n >> m;
    m = min(m, n);
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            dp[i][j] = 1e18;
        }
    }

    dp[0][0] = 0;

    for(int i = 1; i <= n; i++){
        cin >> ar[i];
        sum[i] = ar[i] + sum[i - 1];
    }

    for(int i = 1; i <= m; i++){
        solve(i, i, n, 0, n - 1);
    }

    cout << dp[n][m] << endl;

}