#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 100005, K = 104, INF = 30000 * 10000;
int n, k, A[N], dp[2][N], stk[N];
int mn[N], pref[N];
/*int mn[N * 4], lazy[N * 4];
int le, ri, val;
void Add(int id = 1, int l = 0, int r = n + 1)
{
if (ri <= l || r <= le)
return ;
if (le <= l && r <= ri)
{
lazy[id] += val;
mn[id] += val;
return ;
}
Add(lc, l, md);
Add(rc, md, r);
mn[id] = min(mn[lc], mn[rc]) + lazy[id];
}
int Get(int id = 1, int l = 0, int r = n + 1)
{
if (ri <= l || r <= le)
return (INF);
if (le <= l && r <= ri)
return (mn[id]);
return (min(Get(lc, l, md), Get(rc, md, r)) + lazy[id]);
}
inline void Adder(int _le, int _ri, int _val) {le = _le; ri = _ri; val = _val; Add();}
inline int Getter(int _le, int _ri) {le = _le; ri = _ri; return (Get());}*/
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf("%d", &A[i]);
dp[0][i] = dp[1][i] = INF;
}
A[0] = dp[1][0] = INF;
for (int j = 1; j <= k; j++)
{
int w = j & 1;
int r = 1;
memset(mn, 0, sizeof(mn));
//memset(lazy, 0, sizeof(lazy));
//Adder(0, 1, dp[!w][0]);
dp[w][0] = pref[0] = mn[0] = INF;
for (int i = 1; i <= n; i++)
{
mn[i] = dp[!w][i - 1] + A[i];
while (A[stk[r]] <= A[i])
mn[i] = min(mn[i], mn[stk[r]] + A[i] - A[stk[r]]), r --;
//Adder(stk[r - 1], stk[r], A[i] - A[stk[r]]), r --;
pref[i] = min(pref[stk[r]], mn[i]);
stk[++ r] = i;
dp[w][i] = pref[i];
//Adder(i - 1, i, A[i]);
//dp[w][i] = Getter(0, i);
//Adder(i, i + 1, dp[!w][i]);
}
}
return !printf("%d\n", dp[k & 1][n]);
}
