// prea inapt s o bag cu aint :( arswgtdfsgdfssdfh
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("ferma.in");
ofstream fout("ferma.out");

const int N = 1e4, K = 1e3;
int v[N + 1], prefix[N + 1], dp[K + 1][N + 1];

int main(){

	int n, k;
	fin >> n >> k;

	for(int i = 1; i <= n; i++)
		fin >> v[i], prefix[i] = prefix[i - 1] + v[i];

	for(int i = 1; i <= k; i++){
		int maxi = dp[i - 1][i - 1] - prefix[i - 1];
		for(int j = i; j <= n; j++)
			dp[i][j] = max(dp[i][j - 1], maxi + prefix[j]), maxi = max(maxi, dp[i - 1][j] - prefix[j]);
	}

	int ans = max(0, dp[k][n]);

	for(int i = 1; i <= n; i++)
		dp[1][i] = max(dp[1][i - 1], prefix[i]);

	for(int i = 2; i <= k; i++){
		dp[i][1] = v[1];
		int maxi = 0;
		for(int j = 2; j <= n; j++)
			dp[i][j] = max(dp[i][j - 1], prefix[j] + maxi), maxi = max(maxi, dp[i - 1][j] - prefix[j]);
	}

	for(int i = k; i <= n; i++)
		ans = max(ans, dp[k][i] + prefix[n] - prefix[i]);

	fout << ans << '\n';

	return 0;
}