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

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

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));

	dp[0][1] = 1e9 + 1;
	stack<int> s;
	for(int i = 1; i <= n; ++i){
		cin>>v[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();
		dp[i][1] = min(dp[i-1][1], v[i]);
	}

	dp[0][1] = 0;

	for(int j = 2; j <= k; ++j){
		for(int i = j; i <= n; ++i){
			if(w[i] == w[i-1]){
				dp[i-1][j-1] = max(dp[i-1][j-1], dp[i-2][j-1]);
			}else if(w[i] < w[i-1]){
				int temp = i-1;
				while(temp && w[temp] != w[i]){
					dp[i-1][j-1] = max(dp[i-1][j-1], dp[temp-1][j-1]);
					temp = w[temp] - 1;
				}
				dp[i-1][j-1] = max(dp[i-1][j-1], dp[temp-1][j-1]);
			}
			dp[i][j] = max(dp[w[i]-1][j], dp[i-1][j-1] + v[i]);

		}

	}

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