#include <iostream>
using namespace std;
const int inf = 1e9 + 5;
const int N = 1e5 + 5;
int n, k, a[N], dp[N], bef[N];
pair < int, int > p[N];
int main () {
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
bef[i] = max(bef[i - 1], a[i]);
}
for(int j = 2; j <= k; j++) {
int sz = 0;
for(int i = 1; i <= n; i++) {
int ans = j <= i ? bef[i - 1] : inf;
bef[i - 1] = dp[i - 1];
while(sz and a[i] >= p[sz - 1].first)
ans = min(ans, p[--sz].second);
if(!sz or a[i] + ans < p[sz - 1].first + p[sz - 1].second)
p[sz++] = make_pair(a[i], ans);
dp[i] = p[sz - 1].first + p[sz - 1].second;
}
bef[n] = dp[n];
}
cout << bef[n] << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBpbmYgPSAxZTkgKyA1Owpjb25zdCBpbnQgTiA9IDFlNSArIDU7CgppbnQgbiwgaywgYVtOXSwgZHBbTl0sIGJlZltOXTsKcGFpciA8IGludCwgaW50ID4gcFtOXTsKCmludCBtYWluICgpIHsKICAgIAogICAgY2luID4+IG4gPj4gazsKICAgIAogICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICBjaW4gPj4gYVtpXTsKICAgICAgICBiZWZbaV0gPSBtYXgoYmVmW2kgLSAxXSwgYVtpXSk7CiAgICB9CiAgICAKICAgIGZvcihpbnQgaiA9IDI7IGogPD0gazsgaisrKSB7CiAgICAgICAgaW50IHN6ID0gMDsKICAgICAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewogICAgICAgICAgICBpbnQgYW5zID0gaiA8PSBpID8gYmVmW2kgLSAxXSA6IGluZjsKICAgICAgICAgICAgYmVmW2kgLSAxXSA9IGRwW2kgLSAxXTsKICAgICAgICAgICAgd2hpbGUoc3ogYW5kIGFbaV0gPj0gcFtzeiAtIDFdLmZpcnN0KQogICAgICAgICAgICAgICAgYW5zID0gbWluKGFucywgcFstLXN6XS5zZWNvbmQpOwogICAgICAgICAgICBpZighc3ogb3IgYVtpXSArIGFucyA8IHBbc3ogLSAxXS5maXJzdCArIHBbc3ogLSAxXS5zZWNvbmQpCiAgICAgICAgICAgICAgICBwW3N6KytdID0gbWFrZV9wYWlyKGFbaV0sIGFucyk7CiAgICAgICAgICAgIGRwW2ldID0gcFtzeiAtIDFdLmZpcnN0ICsgcFtzeiAtIDFdLnNlY29uZDsKICAgICAgICB9CiAgICAgICAgYmVmW25dID0gZHBbbl07CiAgICB9CiAgICAKICAgIGNvdXQgPDwgYmVmW25dIDw8IGVuZGw7CiAgICAKICAgIHJldHVybiAwOwogICAgCn0K