/*
TASK: bus
LANG: C++
*/

#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 dp[2][MAXN];

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

	int i, j, k;
	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];
/*
	for (i = 0; i < N; ++i) {
		for (j = i; j < N; ++j)
			printf ("%d %d -- %d\n", i, j, f[i][j]);
		printf ("\n");
	}
*/
	int o = 0, n = 1;
	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;
		pb = N - j;
		for (i = N - j - 2; i >= 0; --i) {
			dp[n][i] = INF;
			for (k = pb; k > i; --k)
				if (dp[n][i] >= dp[o][k] + f[i][k]) {
					dp[n][i]  = dp[o][k] + f[i][k];
					npb = k;
				}
			pb = npb;
		}
		o = n;
		n = !n;
	}

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

	return 0;
}
