#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 1e5 + 10, MAXK = 105;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
long long n, k, a[MAXN];
void read()
{
cin >> n >> k;
for (long long i = 1; i <= n; ++ i)
cin >> a[i];
}
long long dp[MAXN][MAXK];
long long maxused[MAXN][MAXK];
void solve()
{
long long inf = 1e17;
for (int i = 1; i <= n; ++ i)
for (int j = 0; j <= k; ++ j)
dp[i][j] = inf;
dp[0][0] = 0;
for (long long j = 1; j <= k; ++ j)
{
stack < pair <long long, long long > > t;
///t.push(make_pair(0, 0));
for (long long i = j; i <= n; ++ i)
{
///cout << "***" << endl;
dp[i][j] = inf;
dp[i][j] = dp[i-1][j-1] + a[i];
maxused[i][j] = a[i];
long long init = dp[i][j];
if(init >= inf)
{
maxused[i][j] = inf;
}
/// cout << "init " << init << " from " << dp[i-1][j-1] << endl;
while(!t.empty())
{
long long sz = t.top().first;
long long dpp = t.top().second;
if(maxused[sz][j] <= a[i])
{
if(dpp + a[i] - maxused[sz][j] < dp[i][j])
{
dp[i][j] = dpp + a[i] - maxused[sz][j];
/// cout <<"updated to " << dpp + a[i] - maxused[sz][j] << " from " << sz << endl;
}
t.pop();
}
else break;
}
if(t.size() == 0 || t.top().second > dp[i][j])
{
/// cout << "if (1) " << endl;
t.push(make_pair(i, dp[i][j]));
}
else
{
/// cout << "if (2) " << endl;
dp[i][j] = t.top().second;
maxused[i][j] = maxused[t.top().first][j];
}
/// cout << i << " " << j << " --> " << dp[i][j] << endl;
/// cout << "maxused " << maxused[i][j] << endl;
/// cout << "init was " << init << endl;
}
}
cout << dp[n][k] << endl;
}
int main()
{
speed();
read();
solve();
return 0;
}
