#include<iostream>
#include<cstdio>
const int MAX_N = 8000, MAX_G = 800;
const long long INF = 1ll<<62;
int N,G;
long long s[MAX_N+10];
struct {long long val; int opt;} dp[MAX_N+10][MAX_G+10];
inline long long cost(int l, int r) { return (s[r]-s[l-1])*1ll*(r-l+1); }
int main()
{
scanf("%d%d\n", &N, &G);
for (int i = 1; i <= N; ++i)
{
scanf("%d\n", s+i);
s[i] += s[i-1];
}
if (N <= G)
{
printf("%lld", s[N]);
return 0;
}
for (int i = 1; i <= N; ++i)
{
dp[i][i].val = s[i];
dp[i][i].opt = std::max(i-1, 1);
dp[i][1].val = i*s[i];
dp[i][1].opt = 1;
}
for (int i = 2; i <= N; ++i)
for (int j = std::min(G, i-1); j > 1 ; --j)
{
dp[i][j].val = INF;
int to = j==G?i-1:dp[i][j+1].opt;
for (int k = dp[i-1][j].opt; k <= to; ++k)
{
long long val = dp[k][j-1].val + cost(k+1, i);
if (dp[i][j].val > val)
{
dp[i][j].val = val;
dp[i][j].opt = k;
}
}
}
printf("%lld", dp[N][G].val);
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRpbz4KCmNvbnN0IGludCBNQVhfTiA9IDgwMDAsIE1BWF9HID0gODAwOwpjb25zdCBsb25nIGxvbmcgSU5GID0gMWxsPDw2MjsKaW50IE4sRzsKbG9uZyBsb25nIHNbTUFYX04rMTBdOwpzdHJ1Y3Qge2xvbmcgbG9uZyB2YWw7IGludCBvcHQ7fSBkcFtNQVhfTisxMF1bTUFYX0crMTBdOwoKaW5saW5lIGxvbmcgbG9uZyBjb3N0KGludCBsLCBpbnQgcikgeyByZXR1cm4gKHNbcl0tc1tsLTFdKSoxbGwqKHItbCsxKTsgfQoKaW50IG1haW4oKQp7CiAgICBzY2FuZigiJWQlZFxuIiwgJk4sICZHKTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IE47ICsraSkKICAgIHsKICAgICAgICBzY2FuZigiJWRcbiIsIHMraSk7CiAgICAgICAgc1tpXSArPSBzW2ktMV07CiAgICB9CiAgICBpZiAoTiA8PSBHKQogICAgewogICAgICAgIHByaW50ZigiJWxsZCIsIHNbTl0pOwogICAgICAgIHJldHVybiAwOwogICAgfQoKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IE47ICsraSkKICAgIHsKICAgICAgICBkcFtpXVtpXS52YWwgPSBzW2ldOwogICAgICAgIGRwW2ldW2ldLm9wdCA9IHN0ZDo6bWF4KGktMSwgMSk7CgogICAgICAgIGRwW2ldWzFdLnZhbCA9IGkqc1tpXTsKICAgICAgICBkcFtpXVsxXS5vcHQgPSAxOwogICAgfQoKICAgIGZvciAoaW50IGkgPSAyOyBpIDw9IE47ICsraSkKICAgICAgICBmb3IgKGludCBqID0gc3RkOjptaW4oRywgaS0xKTsgaiA+IDEgOyAtLWopCiAgICAgICAgewogICAgICAgICAgICBkcFtpXVtqXS52YWwgPSBJTkY7CgogICAgICAgICAgICBpbnQgdG8gPSBqPT1HP2ktMTpkcFtpXVtqKzFdLm9wdDsKICAgICAgICAgICAgZm9yIChpbnQgayA9IGRwW2ktMV1bal0ub3B0OyBrIDw9IHRvOyArK2spCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGxvbmcgbG9uZyB2YWwgPSBkcFtrXVtqLTFdLnZhbCArIGNvc3QoaysxLCBpKTsKICAgICAgICAgICAgICAgIGlmIChkcFtpXVtqXS52YWwgPiB2YWwpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgZHBbaV1bal0udmFsID0gdmFsOwogICAgICAgICAgICAgICAgICAgIGRwW2ldW2pdLm9wdCA9IGs7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgcHJpbnRmKCIlbGxkIiwgZHBbTl1bR10udmFsKTsKfQ==