// f[i][j] : i:有i个post, j处结束并且j处有一个post
// f[i][j] = min { f[i][k] + cost[k][j] }
// 最后的解应该是 min { cost[k][n+1] + f[m][k] }(k>=m)
// cost[i][j]: i处有一个post, j有一个post
// 数据有点水


#include <stdio.h>
#include <stdlib.h>
#include <math.h>


#define V	(305)
#define P	(35)
#define MAX	(200000)


int a[V];
int f[P][V];    
int cost[V][V]; 


void sum(int pre, int cur)
{
	int s = 0;
	int i = 0;
	for (i = pre+1; i < cur; ++i)
	{
		if (a[i]-a[pre] < a[cur]-a[i])
		{
			s += a[i]-a[pre];
		}
		else
		{
			s += a[cur]-a[i];
		}
	}
	cost[pre][cur] = s;
}



int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	int n = 0;
	int m = 0;
	while (EOF != scanf("%d %d", &n, &m))
	{
		int i = 0;
		int j = 0;
		for (i = 1; i <= n; ++i)
		{
			scanf("%d", &a[i]);
		}
		a[0] = -MAX;
		a[n+1] = MAX;
		for (i = 0; i <= n; ++i)
		{
			for (j = i+1; j <= n+1; ++j)
			{
				sum(i, j);
			}
		}
		if (1 == m)
		{
			int mid = (1+n)/2;
			printf("%d\n", cost[0][mid]+cost[mid][n+1]);
		}
		else
		{
			for (i = 1; i <= n; ++i)
			{
				f[1][i] = cost[0][i];
			}
			for (i = 2; i <= m; ++i)
			{
				for (j = i; j <= n; ++j)
				{
					int k = 0;
					int min = MAX;
					for (k = 1; k < j; ++k)
					{
						int t = f[i-1][k]+cost[k][j];
						if (min > t)
						{
							min = t;
						}
					}
					f[i][j] = min;
				}
			}
			int min = MAX;
			for (i = m; i <= n; ++i)
			{
				if (min > f[m][i]+cost[i][n+1])
				{
					min = f[m][i]+cost[i][n+1];
				}
			}
			printf("%d\n", min);
		}
	}
	return 0;
}