#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
ll in[MAXN];
ll dp[105][MAXN];
int n, blocks;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> blocks;
for(int i = 0; i < n; i++) {
cin >> in[i];
}
dp[1][0] = in[0];
for(int i = 1; i < n; i++)
dp[1][i] = max(dp[1][i - 1], in[i]);
//cout << "hm\n";
for(int block = 2; block <= blocks; block++)
{
stack<pair<int, int> > curr;
for(int i = block - 1; i < n; i++)
{
int mini = dp[block - 1][i - 1];
while(!curr.empty() && in[curr.top().first] <= in[i])
{
mini = min(mini, curr.top().second);
curr.pop();
}
if(curr.empty() || in[curr.top().first] + curr.top().second > in[i] + mini)
curr.push({i, mini});
dp[block][i] = in[curr.top().first] + curr.top().second;
}
}
cout << dp[blocks][n - 1] << "\n";
}
