#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn=1011;
struct node
{
	int id,h;
}P[maxn];
int H[maxn],m,n,lim;
int f[2][maxn][26][2];
bool cmpid(const node &a,const node &b)
{
	return a.id<b.id;
}
bool cmph(const node &a,const node &b)
{
	return a.h<b.h;
}
void init()
{
	scanf("%d%d",&n,&lim);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&P[i].h);
		P[i].id=i;
	}
	sort(P+1,P+n+1,cmph);
	for (int i=1;i<=n;i++)
	{
		if (P[i].h!=P[i-1].h) H[++m]=P[i].h;
		P[i].h=m;
	}
	sort(P+1,P+n+1,cmpid);
}

int min(int a,int b)
{
	if (a==-1) return b;
	if (b==-1) return a;
	return a<b ? a : b;
}

void solve()
{
	memset(f,-1,sizeof(f));
	f[0][0][0][0]=0;
	for (int i=1;i<=n;i++)
	{
		int o=i & 1;
		for (int k=lim;k>=0;k--)
		{
			int minx=-1;
			for (int j=0;j<=P[i].h;j++)
			{
				f[o][j][k][0]=min(minx,f[!o][j][k][0]);
				if (f[o][j][k][0]!=-1) f[o][j][k][0]+=H[P[i].h]-H[j];
				minx=min(minx,f[!o][j][k][0]);
				minx=min(minx,f[!o][j][k][1]);
			}
			minx=-1;
			for (int j=m;j>P[i].h;j--)
			{
				if (k>0)
				minx=min(minx,f[!o][j][k-1][0]);
				minx=min(minx,f[!o][j][k][1]);
			}
			for (int j=P[i].h;j>=0;j--)
			{
				f[o][j][k][1]=min(minx,f[!o][j][k][1]);
				if (f[o][j][k][1]!=-1) f[o][j][k][1]+=H[P[i].h]-H[j];
				if (k>0)
				minx=min(minx,f[!o][j][k-1][0]);
				minx=min(minx,f[!o][j][k][1]);
			}
			for (int j=m;j>P[i].h;j--)
			f[o][j][k][0]=f[o][j][k][1]=-1;
		}
	}
	int o=n & 1;
	int ans=2000000000;
	for (int k=0;k<=lim;k++)
	for (int j=0;j<=P[n].h;j++)
	{
		ans=min(ans,f[o][j][k][1]);
		if (k>0) ans=min(ans,f[o][j][k-1][0]);
	}
	printf("%d\n",ans);
}

int main()
{
	freopen("peaks.in","r",stdin);
	freopen("peaks.out","w",stdout);
	init();
	solve();
	return 0;
}