/*
TASK: bus
LANG: C++
KEYW: dynamical programming with optimization on the inner cycle using a deque :-P, with a binary search cmp function
*/

#include <cstdio>
#include <cstring>

const int MAXN = 1 << 10;
const int INF = 0x3f3f3f3f;

int N, K;
int vec[MAXN];
int sum[MAXN];
int f[MAXN][MAXN];
int o, n;
int dp[2][MAXN];

int cmp (int a, int b) {
	static int l, r, m;
	l = -1, r = b;
	while (l + 1 != r) {
		m = (l + r) / 2;
		if (f[m][b] + dp[o][b]
		 <= f[m][a] + dp[o][a])
			l = m;
		else
			r = m;
	}
//	printf ("cmp %d %d -- %d\n", a, b, l);
	return l;
}

int main () {
	scanf ("%d %d", &N, &K);

	int i, j;
	for (i = 0; i < N; ++i)
		scanf ("%d", vec + i);

	sum[0] = vec[0];
	for (i = 1; i < N; ++i)
		sum[i] = sum[i-1] + vec[i];

	int d;
	for (d = 2; d < N; ++d)
		for (i = 0; i + d < N; ++i)
			f[i][i+d] = f[i+1][i+d-1] + sum[i+d-1] - sum[i];

////////////////////
	o = 0; n = 1;
	static int q[MAXN];
	int p1, p2;

	memset (dp[o], 0x3f, sizeof (dp) / 2);//INF
	dp[o][N-1] = 0;

//	int pb, npb = -1;
	for (j = 1; j < K; ++j) {
		dp[n][N - j - 1] = 0;
		p1 = p2 = 0;
		q[p2++] = N - j;
		q[p2++] = N - j - 1;
		for (i = N - j - 2; i >= 0; --i) {
			dp[n][i] = INF;
			if (cmp (q[p1], q[p1+1]) >= i) ++p1;
			dp[n][i] = dp[o][q[p1]] + f[i][q[p1]];
//			printf ("upd (%d) %d -- %d\n", j, i, q[p1]);
			q[p2] = i;
			while (p2 - p1 >= 2
			 && cmp (q[p2-2], q[p2-1])
			 <= cmp (q[p2-1], q[p2])) {
				q[p2-1] = q[p2];
				--p2;
			}
			++p2;
		}
		o = n;
		n = !n;
	}

	printf ("%d\n", dp[o][0]);

	return 0;
}
