#include <fstream>

using namespace std;

ifstream cin ("ferma.in");
ofstream cout ("ferma.out");

int n, k;

int v[10005], sp[10005];
int dp[10005][1005];

int main() {
  cin >> n >> k;
  for(int i = 1; i <= n; i++)
    cin >> v[i], sp[i] = sp[i - 1] + v[i];
  for(int j = 2; j <= k; j++) {
    dp[j][j] = sp[j];
    int mx = dp[j][j - 1] - sp[j];
    for(int i = j + 1; i <= n; i++) {
      dp[i][j] = max(dp[i - 1][j], sp[i] + mx);
      mx = max(mx, dp[i][j - 1] - sp[i]);
    }
  }
  int ans = 0;
  for(int i = k; i <= n; i++)
    ans = max(ans, dp[i][k]);
  for(int i = 2; i <= n; i++)
    dp[i][1] = max(dp[i - 1][1], sp[i]);
  for(int j = 2; j <= k; j++) {
    dp[j][j] = sp[j];
    int mx = dp[j][j - 1] - sp[j];
    for(int i = j + 1; i <= n; i++) {
      dp[i][j] = max(dp[i - 1][j], sp[i] + mx);
      mx = max(mx, dp[i][j - 1] - sp[i]);
    }
  }
  for(int i = k; i <= n; i++)
    ans = max(ans, dp[i][k] + sp[n] - sp[i]);
  cout << ans;
  return 0;
}