// Source: https://usaco.guide/general/io

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

struct Tata{
	int w;
	long val;
};
int main() {
	int n, k; cin>>n>>k;
	vector<long> v(n+1);
	vector<int> w(n+1);
	vector<vector<long> > dp(n+1, vector<long>(k+1));

	for(int i = 1; i <= n; ++i){
		cin>>v[i];
	}

	stack<int> s;
	for(int i = 1; i <= n; ++i){
		if(s.empty())s.push(i);
		else{
			while(v[i-1] > v[i] && v[s.top()-1] > v[i]){
				s.pop();
			}
			if(v[i-1] < v[i])s.push(i);
		}
		w[i] = s.top();
	}

	//for(int x: w)cout<<x<<' ';

	dp[0][1] = 1e9 + 1;
	for(int i = 1; i <= n; ++i){
		dp[i][1] = min(dp[i-1][1], v[i]);
	}
	dp[0][1] = 0;

	for(int j = 2; j <= k; ++j){
		stack<Tata> uperr_max;
		vector<long> lowerr_max(n+1);
		for(int i = 1; i <= n; ++i){
			if(uperr_max.empty() || uperr_max.top().w < w[i]){
				Tata temp;
				temp.w = w[i], temp.val = dp[i-1][j-1];
				uperr_max.push(temp);
			}else if(uperr_max.top().w == w[i])uperr_max.top().val = max(uperr_max.top().val, dp[i-1][j-1]);
			else if(uperr_max.top().w > w[i]){
				long temp = dp[i-1][j-1];
				while(uperr_max.top().w > w[i]){
					temp = max(temp, uperr_max.top().val);
					uperr_max.pop();
				}
				uperr_max.top().val = max(uperr_max.top().val, temp);
			}

			dp[i][j] = max(dp[w[i]-1][j], uperr_max.top().val + v[i]);

		}

	}

	cout<<dp[n][k]<<endl;
}