rt /kel

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;
typedef double db;

const int MAXN = 2e3 + 10;

priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int>> q2;

ll s1, s2;

inline 
void clear() {
	for (s1 = 0; !q1.empty(); q1.pop());
	for (s2 = 0; !q2.empty(); q2.pop());
}

inline 
void insert(int x) {
	q2.empty() || x > q2.top() ? q2.push(x), s2 += x : (q1.push(x), s1 += x);
	if (q1.size() > q2.size() + 1) { s2 += q1.top(), s1 -= q1.top(), q2.push(q1.top()), q1.pop(); }
	if (q2.size() > q1.size() + 1) { s1 += q2.top(), s2 -= q2.top(), q1.push(q2.top()), q2.pop(); }
}

inline 
ll query() {
	ll x = q1.size() > q2.size() ? q1.top() : q2.top();
	return (q1.size() - q2.size()) * x - s1 + s2;
}

int n, m, a[MAXN];

ll f[MAXN][MAXN], dp[MAXN][30];

int main() {
	for (; scanf("%d%d", &n, &m), n | m;) {
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++) {
			clear();
			for (int j = i; j; j--) insert(a[j]);
		}
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= m; j++) dp[i][j] = 0x3f3f3f3f3f3f3f3fll;
		}
		**dp = 0;
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j <= i && j <= m; j++) {
				for (int k = 1; k <= i; k++) {
					dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + f[k][i]);
				}
			}
		}
		printf("%lld\n", dp[n][m]);
	}
}