#include <bits/stdc++.h>
#ifdef __DEBUG__
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const deque<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const set<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int N,K;
vector<ll> H;
void input(){
    fast_io();
    cin >> N >> K;
    H.push_back(0);
    for (int i = 0; i < N; i++)
    {
        ll h; cin >> h;
        H.push_back(h);
    }
}

int WAsolve(){
    // vector<bool> changed(N,false);
    for (int k = 0; k < K; k++)
    {    
        vector<ll> changeSim(N,0);
        for (int i = 0; i < N; i++)
        {
            if(i==0){
                if(H[i]>H[i+1]) changeSim[i] = abs(H[i+1]-H[i]);
            }
            else if(i==N-1){
                if(H[i-1]<H[i]) changeSim[i] = abs(H[i-1]-H[i]);
            }
            else{
                if(H[i-1]<H[i] && H[i]>=H[i+1]){
                    // 負の値になる.
                    changeSim[i] = abs(H[i+1]-H[i]);
                }
                else if(H[i-1]>=H[i] && H[i]<H[i+1]){
                    // 正の値になる.
                    changeSim[i] = abs(H[i+1]-H[i]);
                }
            }
        }
        auto itr = max_element(changeSim.begin(),changeSim.end());
        int idx = itr-changeSim.begin();
        if(*itr==0) idx=0;
        H.erase(H.begin()+idx);

        // auto itrm = min_element(changeSim.begin(),changeSim.end());
        // int idx;
        // if(abs(*itrM)>abs(*itrm)){
        //     idx = itrM-changeSim.begin();
        //     H.erase(H.begin()+idx);
        // }
        // else{
        //     idx = itrm-changeSim.begin();
        //     H.erase(H.begin()+idx);
        // }
        N--;
        // DBG(idx)
        // if(idx==0 || idx==N-1) H[idx] = 0;
        // else H[idx] += changeSim[idx];
        // DBG(H)
        // if(changed[idx]) k--;
        // changed[idx] = true;
    }
    DBG(H)
    ll ans = H[0];
    for (int i = 0; i < N-1; i++)
    {
        if(H[i+1]>H[i]) ans+=H[i+1]-H[i];
    }
    cout << ans << endl;
    return 0;
}   

void chmin(ll &a, ll b){if(a>b) a=b;}

int solve(){
    // dp[i][last][k] 左からiまでみて、k個削除したときの操作の最小値.lastは残ってるHiの一番右のidx
    vector<vector<ll>> dp(N+2,vector<ll>(K+2,LL_INF));
    dp[0][0] = 0;
    for (int i = 1; i <= N; i++)
    {
        vector<vector<ll>> tmp(N+2,vector<ll>(K+2,LL_INF));
        for (int last = 0; last < i; last++)
        {
            for (int k = 0; k <= K; k++)
            {
                chmin(tmp[i][k],dp[last][k]+max(H[i]-H[last],0LL));
                chmin(tmp[last][k+1],dp[last][k]);
            }   
        }
        dp = tmp;
    }
    ll ans = LL_INF;
    for (int last = 0; last <= N; last++)
    {
        chmin(ans,dp[last][K]);
    }
    cout << ans << endl;
    
    return 0;
}

int main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 1780