// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 1e5 + 5;
const int K = 1e2 + 5;
const long long INF = 1e18 + 5;
int n, k, a[N];
vector<pair<int, long long>> best[K];
vector<long long> prefMin[K];
inline void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 0; i <= k; i++)
{
best[i].clear();
prefMin[i].clear();
}
best[0].push_back({0, 0});
prefMin[0].push_back(0);
for (int x = 1; x <= n; x++)
{
for (int y = k; y >= 0; y--)
{
long long mn = INF;
while (!best[y].empty() && best[y].back().first <= a[x])
{
mn = min(mn, best[y].back().second);
best[y].pop_back();
prefMin[y].pop_back();
}
if (!best[y].empty())
{
mn = min(mn, prefMin[y].back() - a[x]);
}
if (mn == INF)
continue;
long long val = mn + a[x];
best[y].push_back({a[x], mn});
if (prefMin[y].empty())
prefMin[y].push_back(val);
else
prefMin[y].push_back(min(prefMin[y].back(), val));
best[y + 1].push_back({0, val});
if (prefMin[y + 1].empty())
prefMin[y + 1].push_back(val);
else
prefMin[y + 1].push_back(min(prefMin[y + 1].back(), val));
}
}
cout << prefMin[k].back();
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
solve();
return 0;
}
