//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <chrono>
#include <cassert>
#include <bitset>
#include <random>
 
using namespace std;
 
typedef long long li;
typedef  long double ld;
const li MAX = 3e5 + 20;
 
li inf = (li)1e15;
li mod = (li)998244353;
 
li dp1[MAX], dp2[MAX], p[MAX], cool[MAX];
li n, k, a[MAX];
 
void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
 
    vector<li> cur;
    for (int i = 1; i <= n; i++) {
        while (cur.size() && a[cur.back()] < a[i]) cur.pop_back();
        if (cur.size()) p[i] = cur.back();
        cur.push_back(i);
    }
    li cur_max = a[1];
    dp1[0] = inf;
    dp2[0] = inf;
    for (int i = 1; i <= n; i++) {
        cur_max = max(cur_max, a[i]);
        dp1[i] = cur_max;
    }
 
    for (int j = 2; j <= k; j++) {
        vector<li> cur = { 0 };
        for (int i = 1; i <= n; i++) {
            dp2[i] = inf;
            li uk1 = -1, uk2 = cur.size();
            while (uk2 - uk1 > 1) {
                li mid = (uk2 + uk1) / 2;
                if (cur[mid] >= p[i]) uk2 = mid;
                else uk1 = mid;
            }
            if (uk2 != cur.size()) dp2[i] = min(dp2[i], dp1[cur[uk2]] + a[i]);
            while (cur.size() && dp1[cur.back()] > dp1[i]) cur.pop_back();
            cur.push_back(i);
        }
        for (int i = 1; i <= n; i++) {
            dp2[i] = min(dp2[i], dp2[p[i]]);
        }
 
        for (int i = 0; i <= n; i++) dp1[i] = dp2[i];
    }
    cout << dp1[n];
}
 
int main() {
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios::sync_with_stdio(0);
    li q;
    q = 1;
    while (q--) solve();
 
    return 0;
}