#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

#define pii pair<int, int>

int random(int a, int b) {
	static random_device rd;
	return uniform_int_distribution<int>(a, b)(rd);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifdef CB
	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int N = 10000, K = 5000;
	cin >> N >> K;
	int v[N + 1];
	for (int i = 1; i <= N; i++) {
		v[i] = random(1, 1000000000);
		cin >> v[i];
	}
	int dp[K + 1][N + 1];
	for (int i = 1; i <= N; i++) {
		dp[0][i] = -1e9;
	}
	pii a[N];
	int b[N + 1];
	for (int i = 1; i <= K; i++) {
		dp[i - 1][0] = 0;
		b[0] = 0;
		int c = 0;
		for (int j = 1; j <= N; j++) {
			int m = dp[i - 1][j - 1] + v[j];
			while (c > 0 && a[c - 1].first > v[j]) {
				m = max(m, a[c - 1].second - a[c - 1].first + v[j]);
				c--;
			}
			a[c++] = {v[j], m};
			dp[i][j] = b[c] = max(b[c - 1], m);
		}
	}
	cout << dp[K][N] << endl;
	return 0;
}