#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n , p , d[3005] , f[3005][305] , m[3005][3005];
int main(){
	scanf ("%d%d" , &n , &p);
	for(int i = 0; i < n; i ++)scanf ("%d" , &d[i]);
	for(int i = 0; i < n; i ++)
		for(int j = 0; j <= min(i , p - 1); j ++)
			f[i][j] = 0x3f3f3f3f;
	for(int i = 0; i < n; i ++){
		for(int j = i + 1; j < n; j ++)
			m[i][j] = m[i][j - 1] + d[j] - d[i + j >> 1];	
		f[i][0] = m[0][i];
	}
	for(int i = 1; i < n; i ++)
		for(int j = 1; j <= min(i , p - 1); j ++)
			for(int k = j - 1; k < i; k ++)
				f[i][j] = min(f[i][j] , f[k][j - 1] + m[k + 1][i]);
	printf ("%d" , f[n - 1][p - 1]);
	return 0;
}