#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstring>
#include <string>
#include <set>
#include <unordered_set>
#include <bitset>
#include <limits>
#include <climits>
#include <queue>
#include <deque>
#include <list>
#include <forward_list>
#include <sstream>
#include <complex>
#include <iterator>
#include <functional>
#include <tuple>
#include <array>
#include <locale>
#include <memory>
#include <cstdio>
#define fin(x) freopen("input.txt", "r", stdin);
#define fout(x) freopen("output.txt", "w", stdout);
#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define cp(x) cout.setf(ios::fixed); cout.precision(x);
#define loop(x, n) for(int i = x; i <= n; ++i)
#define FOR(x, n, y) for(int i = x; i <= n; i += y)
#define FORN(x, n, y) for(int y = x; y <= n; ++y)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mem(a,b) memset(a, b, sizeof(a))
#define mcp(a,b,x) memcpy(a, b, sizeof(x))
#define wh(t) while(true)
#define sp system("pause")
#define ST(N) srand(time(NULL))
#define SQ(x) (x)*(x)
#define ppc(x) __popcnt(x)
#define lb lower_bound
#define ub upper_bound
#define tp toupper
#define tl tolower
#define ad push_back
#define em emplace
#define eh empalce_hint
#define mp make_pair
#define nxp next_permutation
#define fr first
#define sc second
#define cl clear
#define vc vector
#define pq priority_queue
#define bs bitset
#define li list<int>
#define vi vector<int>
#define si set<int>
#define vii vector<vector<int> >
#define sti stack<int>
#define dqi deque<int>
#define pqi priority_queue<int>
#define pii pair<int, int>
#define mii map<int, int>
#define bs32 bitset<32>
//#define DEBUG
//#define TEST 1
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
typedef long long ll;
typedef long double ld;
typedef double dbl;
typedef unsigned long long ull;
using namespace std;
const int N = 1000 * 1000 + 100;
const ll MOD = 1e9 + 7;
const ll INC = INT_MAX;
const ll INF = LLONG_MAX;
const ull EPS = ULLONG_MAX;
long long minim = INF;
long long maxim = -INF;
long long cnt = 0, ans = 0;
vector<int> dp(N);
bool u = false, U[N];
int a[N], b[N], c[N];
int A[N / 1000][N / 1000];
string s, t;
vector<int> G[N];
vector<int> parent(N), D(N);
vector<char> color(N, false);
void bfs(int s) {
queue<int> q;
color[s] = true;
q.push(s);
while (!q.empty()) {
s = q.front(); q.pop();
for (int i = 0; i < G[s].size(); ++i) {
if (G[s][i] > 0 && !color[G[s][i]]) {
color[G[s][i]] = true;
q.push(G[s][i]);
}
}
}
}
void dfs(int v) {
color[v] = true;
for (int i = 0; i < G[v].size(); ++i) {
if (G[v][i] > 0 && !color[G[v][i]]) {
color[G[v][i]] = true;
dfs(G[v][i]);
}
}
}
void dfs(int v, int p)
{
D[v] = D[p] + 1;
for (auto to : G[v]) {
if (to != p) dfs(to, v);
}
}
void make_set(int v) {
parent[v] = v;
}
int find_set(int v) {
if (v == parent[v]) return v;
return parent[v] = find_set(parent[v]);
}
int pre[N]; pii p[N];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define USACO
#ifdef USACO
#ifndef _MSC_VER
#define TASK ""
freopen(TASK".in", "r", stdin);
freopen(TASK".out", "w", stdout);
#endif
#endif
int n, k; cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pre[i] = max(pre[i - 1], a[i]);
}
int cnt = 0;
for (int j = 2; j <= k; ++j) {
int size = 0;
for (int i = 1; i <= n; ++i) {
if (j <= i) cnt = pre[i - 1];
else cnt = 1000 * 1000 * 1000;
pre[i - 1] = dp[i - 1];
for (; size != 0 && a[i] >= p[size - 1].first;) {
--size;
cnt = min(cnt, p[size].second);
}
if (!size || cnt + a[i] <p[size - 1].first + p[size - 1].second) {
p[size] = mp(a[i], cnt);
++size;
}
dp[i] = p[size - 1].fr + p[size - 1].sc;
}
pre[n] = dp[n];
}
cout << pre[n] << endl;
return 0;
}
